列 \(x_1, \cdots, x_k (x_1 < \cdots < x_k)\) が与えられたとき、この \(k\) マスにコインがあり、他のマスにコインがない状態に到達可能か判定してみましょう。

まず、\(x_1 \mod 3, \cdots, x_k \mod 3\) の値のみが重要であることに注意します。なぜなら、

...# -> #### -> #...

という操作を行うことで、「添字の値 mod \(3\)」を保ったまま任意の状態を「極小」な状態に変換できるためです。

したがって、次の問題を得ます。

• 空の文字列がある。文字列 012, 120, 201 を任意の位置に挿入することができる。また、012, 120, 201 のいずれかであるような部分文字列を文字列から削除することができる。与えられた目標文字列を作ることは可能か。

削除操作を行う必要はないことが証明できます。削除操作を挿入操作の直後に行うなら、

• 二つの操作が行われる位置に共通部分がない場合、この二操作は入れ替えられます（これを可能な限り繰り返し、削除操作を前倒ししていきます。このプロセスはいずれ終わります）
• そうでなければ、二つの操作は打ち消し合います。例: 01 -> 01201 -> 01（201 を挿入して 012 を削除しましたが、何も変わっていません）

まとめると、列 \(x_1, \cdots, x_k\) に到達可能なのは、ある \(p, q, r (p < q < r)\) に対して次が満たされるときです。

• \(x_q = x_p + 1, x_r = x_p + 2 \pmod 3\)
• 列 \(x_1, \cdots, x_{p-1}\) に到達可能である。
• 列 \(x_{p+1}, \cdots, x_{q-1}\) に到達可能である。
• 列 \(x_{q+1}, \cdots, x_{r-1}\) に到達可能である。
• 列 \(x_{r+1}, \cdots, x_{k}\) に到達可能である。

ここから、\(O(N^3)\) の DP による問題の解法が容易に得られます。