結果
時間ギリギリの4完。先週は時間ギリギリの３完だったのでホッとしました。しかし、D問題を早解きできるようにならないと水色にはなれなそうです。
A問題
最近、A問題が難しい気がします。前回に引き続き、問題の理解に時間がかかりました。
B問題
0-indexと入力を合致させるための-1を入れる場所を間違えてWA。無能が無能たる所以です。
C問題
３日目終了時点で上位k番に入っている人は、下位の人が全員０点を取れば、当然k番目に入れます。上位k番に入っていない人は、ちょうどk番目の人が０点をとって、自分が満点を取った場合に、その人を追い越せるか否かのみを判断すればいいです。C問題は先週のコンテストでトラウマになっていたので、解ききることができてよかったです。
D問題
「どこまでずらすか」という操作を高速化しなければいけない問題だということは最初の5分で気づけました。成長を感じました。しかし、高速化手法が全く思いつきませんでした。自分が成長できていないことを痛感しました。結論、成長できていないことを痛感しました。
まず、次に移るべきindexを辞書で管理するという謎の方法を実装し、WA。1分考えたらバグだらけであることに気づきました。提出する前に立ち止まって考えるべきでした。
どうしても高速化手法が思いつかず、実行時間制限4secを見て、意外と高速化しなくても通るんじゃないかなんていう淡い期待を抱いて、愚直にずらして提出。祈りは届かずTLE。
E問題をWAしたのち、D問題に帰ってきて考察を再開。「区間ごとにまとまりを作っていきたい」と感じて、何かしらをまとめて行くのにUnion-Findを使ったことがあるのを思い出しました。まだ使われていない場所を親とみなして実装。親が保持する負の値は、そこから何個連続で既に使われているかを表します。ある入力xから、どこまでずらすかを考える時は、まずはxの親を探して、親のindex-親が保持している値を計算すれば良いです。
元々自分が書いたことのあるUnion-Findは、indexが若いものが親になるというものでしたが、今回はそうとは限らなかったのでWA。どちらが親になるのかを適切に書き直してなんとかACできました。WAしまくった問題が通った瞬間の喜びは測り知れません。
E問題
「m^(k^n)だと思うんだけど、、、」→「一応、サンプル通してみよう」→「え、どっちも通るんですけど。」→「提出じゃああああ」→「知ってた。」でD問題に帰りました。
この問題はフェルマーの小定理たるものを以下に理解しているかを問うてきた問題だったと思います。過去問を解く中で何度か出てきたのですが、よくもわからず、xで割るときの998244353のあまりは、x^(998244353-2)をかけた時のあまりに等しいというのを暗記したのみでした。「いい加減な学習してないですか？」って出題者の方に指摘された気がします。
pが素数でaがpの倍数でない時、a^(p-1)%p=1。しっかり覚えました。理解できていたとして、解けていたかは別問題です。あはは。
総括
新しい問題を解くだけでなく、一度解いた問題を解き直す必要がある気がしました。
余談
ac-predictorという便利ツールをインストールすると、コンテスト中にリアルタイムで自分の現在のレート遷移がわかります。とても便利です。使ってない方は是非使ってみてください！
