AGC 036 B - Do Not Duplicate

• 問題
• AC

$s$を操作していく中で、$s$の先頭の数と同じ数が現れたとき、またその時に限ってすべての数が消えることに注目する。

数列$A := (3, 2, 4, 3, 4, 1)$を例にとって考える。$s$の先頭が$A_0(=3)$である場合、$A_1(=2)$である場合、…の$n$通りについて、$A$を右にひとつつなげた時に、数が全部消えて次に始まる位置を考える:

• 3 2 4 3 4 1 | 3 2 4 3 4 1
• X 2 4 3 4 1 | 3 2 4 3 4 1
• X X 4 3 4 1 | 3 2 4 3 4 1
• X X X 3 4 1 | 3 2 4 3 4 1
• X X X X 4 1 | 3 2 4 3 4 1
• X X X X X 1 | 3 2 4 3 4 1

つまり、$A$をひとつ追加すると先頭の位置は

$0 \mapsto 3 \\ 1 \mapsto 2 \\ 2 \mapsto 6 \\ 3 \mapsto 1 \\ 4 \mapsto 3 \\ 5 \mapsto 6$

と変化していることになる。ここで位置$6$が登場しているが、つまり、先頭が存在しない場合も扱う必要があった。すなわち

• X X X X X X | 3 2 4 3 4 1

も追加して

$0 \mapsto 3 \\ 1 \mapsto 2 \\ 2 \mapsto 6 \\ 3 \mapsto 1 \\ 4 \mapsto 3 \\ 5 \mapsto 6 \\ 6 \mapsto 0$

が完全な対応である。この写像を$K-1$回合成すれば、そこからはシミュレーションで間に合う。合成にはダブリングが使える。

---

開始位置を$n$通りではなくて$n+1$通り考える必要がある、という部分を明確にできなくてコンテスト中には書けなかった。

あと、写像を作る部分を${\mathcal O}(N)$で実装するのに時間がかかった。こういうのは問題数をこなすしかなさそう。