AGC036 B - Do Not Duplicate (700)
A中の各位置で次に自身と同じ数値が出てくる位置をメモしておく
後ろに同じ数値が無い場合、前から見ていく
0番目から始めて同じ数字の次の位置に飛んでその次の位置から始めるというのを繰り返す
0番目の位置まで戻ってくるまでの周期をシミュレーションで求める
この周期は操作後の数列が空になるタイミングなのでkを周期で割ることができる
残りのk回を同様にシミュレーションすることで答えの配列を得られる
次の出現位置のメモが$ O(N)
シミュレーションは最悪$ O(N^2)だと思っていたが、各位置について飛ぶ位置か飛ぶ先の2回しか現れないはずなので$ O(N)
なので全体でも$ O(N)