Codeforces Round #625 (Div. 1, based on Technocup 2020 Final Round)

　A, Bの二完。Cはやり方は分かったけど実装が終わらず、という苦しい回。

コンテストへのリンク

A. Journey Planning

　A[i]-iを考える問題は結構よく出題されてますね。

　（類題を貼ろうと思ったけど、思い出せなかった……）

B. Navigation System

　終点からBFSをしておけば、各点から次にどの点たちへ行くときが最短経路に含まれるかは分かる。

C. World of Darkraft: Battle for Azathoth

　Misterさんのブログや、けんちょんさんのブログに解説があります。

こういう問題は二次元平面上に図示すると分かりやすい。（というか、そうしないと考察するのは無理だと思っている）

・二次元平面上に図示→x, yの片方を固定

　という流れは頻出（たとえば、SRM778のDiv1 Easyとか）。
　特に、xとyが対称のとき、対称性を崩すことに躊躇いを覚えてしまいがちだけど、片方固定で解ける（計算量が落ちる）ことは良くあるので注意しておきたい。

　その後の実装も大変だけど、できなくてはいけないのかなぁ。

　なお、PyPyだと時間制限がやや厳しいです。
　まつかわさんとのやりとりで、こういう知見が得られました。

　INF=1<<31　と1<<31で型が違うのは、前者だと値が変化するかもしれないので、多少安全を取って型を決めているのかなぁ、と想像しています。（本当のところは分かりません）

D. Reachable Strings

　けんちょんさんの解説記事を読んで解説AC。

　同じ方針で解くのは芸がないので、Suffix-arrayを使おうかと思ったけれど、上手くやることができず、結局同じ方針（Rolling Hash）でACしました。

　ところで、Rolling Hashのmodの選択の仕方が理解できてませんでした。2ベキ+1を愛用（？）していたのですが、それをいくつか重ねてもWrong Answerが出てしまった。ランダムな奇数に変えたらACできたけれど……。

　この辺も理解しなくちゃなぁ、と思ったらmaspyさんがまとめてくれていました。証明は追えていませんが、そもそも基数を乱択すべきということすら知らなかった……。