AGC036-B "Do Not Duplicate" の周期性について
問題
この問題は、周期性をO(N)で求めることができて、それを使って解けるらしいが、以前はそれが理解できなかった。
結局、その時はダブリングを使って解いた。
悔しかったので改めて考え直し、なんとか証明を理解できた（と思う）。
ネット上で見つかるこの周期性についての解説記事では、説明が簡潔だったり、高度に数学チックだったりで、自分には理解できないものが多くて苦労した。
そこで、証明の過程をメモしておく。
概要
問題の入力例4を例にとって考える。
元の数列は {3 1 4 1 5 9 2 6 5 3 5} なので、問題の手順を進めていくと、以下のように状況が進む。
以下の色分けは、処理が始まって、一度数列が空になるまでを示す。（例えば最初の赤色の部分で言うと、先頭の３がもう一度出たときに数列が空になる）
この動き1つ1つを、3の直前から次の3の直後にジャンプする感覚で、「ジャンプ」と呼ぶことにする。
この例の場合、3から5、5から9、9から2にジャンプしている。
[3 1 4 1 5 9 2 6 5 3] [5
3 1 4 1 5][9 2 6 5 3 5
3 1 4 1 5 9] [2 6 5 3 5
このジャンプについて、以下のことが成り立つと色んな記事で言われていた。
・「初期状態（a0=3を数列sに加える前の状態）から、何ジャンプ目（何回数列が空になったか）に再び先頭（数列sが空の状態で、次に数列に追加しようとする要素がa0である状態）に戻ってくるか」を、O(N)でシミュレーションして求めることができる
これができれば、（操作の回数の計算などはとりあえず置いておくとして、）確かに計算量的には「O(N)で求め、操作回数がKを超えないギリギリのところまで周期を使って処理をすっ飛ばし、残りを愚直にシミュレーションする（残りの操作回数はK%（1周期のジャンプ数）なので間に合う」という感じはするけど、本当にそうなのか疑問だったし、やり方も分からなかった。
疑問に思った箇所
色々と分からなかったが、大きく3つの疑問があった。
1. ジャンプ回数は少ないかもしれないが、操作の回数はそれよりずっと多い。その処理はどうすればいいのか。その処理は本当にO(N)で間に合うのか
2. そもそも、本当にどこかで周期するのか
3. 周期するとして、初期状態には必ず戻ってくるのか（どこか途中の箇所でグルグルとループしてしまうことはないのか）
疑問1. ジャンプをどのように計算するか
各ジャンプを考えるとき、愚直に1つずつ操作を進めていくと、到底間に合わないので、工夫する必要がある。
入力例4で考える。
まず、数列内の各要素（Ai）を同じ数毎に分け、「どのインデックスで登場したか（何番目に登場したか）」を配列として持っていく。
数列が{3 1 4 1 5 9 2 6 5 3 5}なので、以下のような形（0-indexed）。
1 : {1, 3}
2 : {6}
3 : {0, 9}
4 : {2}
5 : {4, 8, 10}
6 : {7}
9 : {5}
こうすると、「どこの直前からジャンプすると、どこの直前に着地するか」を求めることができる。
例えば、a1=1 の直前からジャンプすると、次に1が出るのはa3なので、a4の直前にジャンプする。
また、a4=5 の直前からジャンプすると、次に5が出るのはa8なので、a9の直前にジャンプする。
a7=6の直前からジャンプすると、次に6が出るのは同じくa7なので、a8の直前にジャンプする。
このように、各配列内に入れたインデックスに順番に着目していくことで、「どこからどこにジャンプするか（遷移元と遷移先）」をO(N)で確認することができる。
具体的には、今回の場合だとスタート地点がa0=3なので、0->10->5->6->7->8->0 となって戻ってくる。
また、「各ジャンプにつき、実際の操作回数は何回か」というのも、登場するインデックスの差分を取れば求められるから、先程の疑問1.は解決できたことになる。
（もちろん、疑問2. 3.の周期性が前提となる。周期性がなければ、結局、O(K<=10^12)回計算しなくてはならず間に合わない。）
疑問2. そもそも本当にN回で周期するのか
これは比較的簡単に証明することができる。
（自分はよく考えないと分からなかったが、多くの人にとっては自明のことかもしれない。）
N回ジャンプしても、周期しなかったとする。
すると、
[スタート地点→1回目の遷移先→2回目の遷移先→……→N回目の遷移先]
上記のスタート地点及び各回のジャンプ先が全て異なっている、つまりN+1個の異なる地点が存在することになる。
しかし、地点の数はNしかない（地点とは、1<=i<=Nのことだから）ので、そんなことはありえない。
よって、N回以内に戻ってくるということになる。
というか、分かってみれば当たり前のことだった。
N回以上ジャンプするのに、N個しか地点が無いのだから、どっか同じ場所に2回以上ジャンプするに決まってる（＝周期する）。
ちなみに、このことを「鳩の巣原理」というらしい。
当たり前のことのようだが、突き詰めるとすごく役に立つらしく、調べたらなかなか面白かった。
鳩の巣原理 - Wikipedia
疑問3. 本当に初期状態に戻ってくるのか
周期することは分かったが、本当に初期状態に戻ってくるのか。
どこか別の地点でループしてしまって、初期状態に戻ってこないことはないのか。
これも個人的にはわりと難しかった。
背理法で考える（そんな大げさなものでもないけど……）。
「初期状態に戻ってこず、別の場所で周期してしまう」というのは、以下のような状態である。
この図では、1からスタートして、1->2->3->4->5->2->3……と、2から先でループしてしまい、スタート地点の1に戻ってこない。
こういうことはありえない、と証明したい。
この図ではどうしてこうなってしまったのかと考えてみると、「地点２に、地点１と地点５の両方から遷移しているから」ということが分かる。
つまり、「異なる地点から、ある同じ地点に遷移する」ということがあるようだと、スタート地点以外でループしてしまうことがありえる、ということが分かる。
そういうことはあるのか。
2パターンに分けて考えてみる。
[先]は、「遷移先」を示す。
[消]は、今回のジャンプで消える先頭と末尾の部分（同じ数字を持つai）を示す。
※ここで地味に大事なのは、「ある場所に遷移してくる」ためには「直前の数字が出てきたとき、先頭の数字が同じ数字である」必要があるので、[先]の直前は必ず[消]であるということ。
１）[消]が数列内に1つしかないパターン
＊＊＊＊＊＊＊＊＊消先
この場合、[先]に遷移するパターンは「[消]の直前からスタートして、次の周の[消]がきた瞬間に全て消える」という1パターンしかない。
つまり、異なる遷移元から遷移してくることはありえない。
２）[消]が数列内に複数あるパターン
＊消Ａ＊＊＊消Ｂ＊消先
この場合、1つ目の[消]がスタート地点なら、以下の図のとおり2つ目の[消]を見た時に全消しとなり、Bに遷移してしまう。
＊消Ａ＊＊＊消Ｂ＊消先
2つ目の[消]がスタート地点なら、[先]が遷移先となる。
＊消Ａ＊＊＊消Ｂ＊消先
3つ目の[消]がスタート地点なら、次の周で1つ目の[消]を見た時に全消しとなり、Aに遷移してしまう。
＊消Ａ＊＊＊消Ｂ＊消先
以上から、別の遷移元から同じ遷移先に遷移しようとしても、できないことが分かった。
すると、スタート地点から遷移していった先で、スタート地点に戻ってくる前にループしてしまうことはありえないので、疑問3.も解消された。
まとめ
疑問3. の考察で、別の場所でループせず、必ず初期状態に戻って来ることが分かった。
疑問2. の考察で、そのループは、N回以内のジャンプで成されることが分かった。
疑問1. の考察で、O(N)で前計算をしておけば各ジャンプはO(1)で計算でき、N回のジャンプはO(N)で計算できることが分かった。
よって解ける！ 勝利！
（実際には通してないのでコードはありません。ダブリングで一度通したのでいいやってことでサボりました。）
