ABC013 D - 阿弥陀
D - 阿弥陀
提出コード
こういう系の問題は思いつかなければとにかく自作のケースでもテストケースでもいいので実験をしてみるのが一番かなと思っています。
ということでサンプル1および2で実験をしてみると、
左から2番目以外の縦線は、あみだくじをどんどん縦につなげていくことで
1→4→3→5→1→4→...
とループをしていることがわかります。
一番上で、3,4,5からスタートした場合も、上と同じような順番でループをします。
一方で、左から2番目のみ、
2→2→2→...
とずっとその場で留まりつづけます。
どうやら、ループはあみだくじの作り方によって、いける場所が決まっているようです。
ということで、まずはループを洗い出してしまいます。
手順としては、
縦につなげない、1個だけのあみだくじについて、始点をiとしたときのゴール地点を、全てのiについて求める。
これは、まず配列を用意して、その添え字を配列の中身にします。そして、入力を順番に辿っていってその番号を交換していくと、入力完了後には「ゴールをiとしたときの始点の位置」がそれぞれの配列に格納されます。なので、これをまたひっくりかえせば求めることができます。求めたあみだくじについて、ループがどうなっているかを調べる
動的配列を十分な数だけ用意します。
最初にいた場所に戻ってくるまで、あみだくじをたどればよいです。
すでに調べ終わっているループを再び調べることが無いようにすれば、O(N)で求めることができます。
ということで、ループを調べ終わりました。
あとは答えの出力ですが、これまたいちいちたどっているとキリがありません。ので、余りを活用しましょう。
1ループあたりの数は、動的配列の大きさになっています。ので、Dをその大きさで割ったあまりだけ移動した場所をみれば、それが答えになっています。
あとはこれをすべての点についてみていけば、答えとなります。
実装は、AtCoderにしては重めかなという印象です。というより、自分が配列の添え字関連でバグらせやすいだけなのですが…w
