AtCoder Beginner Contest 167 D問題ループ構造を捉える

問題へのリンクはこちら

街１からスタートして、N個の街をK回移動していく。K回の間に行かない街もありえる。問題はKが最大10^18と大きいので、愚直に計算していくと間に合わない、ということだ。

計算量についての一般的な話は下記のけんちょんさんの記事参照。

一方、Nは2×10^5と十分小さい。K>Nの場合、鳩の巣原理から、いくつかの街を複数回訪れることがわかる。そして、とある街にいる際に次にいる街は必ず定まることから、最後は閉ループになっていることがわかる。

例えば例1を考えてみると、街1→街3→街4→街1→...

とループしている構造に見える。これから、Kをループ内の個数で割ったあまりを考えたら計算量を楽できそうという予想がつく。

例えば3N回移動したときはいつも街1にいる。3N+1なら街3、3N+2なら街4だ。

この問題は例が優しいので、次に入力例2を見ると、より問題への理解が深まる。

次は

(街1→街6→)街2→街5→街3→街2→...となっていて、ループの中に入るまでに二つの街を経由している。一度ループに入ったら出てこないので、ループ前の街をうまく考えてあげて、ループに入った後の移動回数をループ内の町の個数で割った余りに着目してあげれば良さそうだ。

そこで、町の順番を把握するためにwhile文で街1からスタートして、一回行ったことがある街までたどり着くまで街の順番を覚える。ここでは例えば可変長配列vに訪れた街の番号を詰めることを考える。N<2×10^5なのでこの計算は十分早く終わる。

ループ前の街の個数をN_out、ループ内の街の個数をN_loopとすると、K-N_outがループの中で移動する回数であることに気をつければ

d=(K-N_out)%(N_loop)でループ内での移動後の位置がわかる。

さっきの町の順番の配列vには、ループ前の街も含めて考えている。そこで、v[N_out+d]とすれば答えの町の場所がわかる。