この問題の想定解は，実験（あるいはエスパー）から乱択に思い至ることです． サンプルに \(N = 10\) のケースが置いてあるので，\(2^{10}\) 通りの色の列に対して操作を試してみると，その半数以上が解として相応しい（操作後に現れ得ない）ことが確認できます． さらに，\(N \le 20\) 程度の小さい入力例をいくらか生成して試してみると，やはり半数以上が解として相応しい（しかもその割合は \(N\) に関して増加傾向である）ことが確認できます． そこで，大きい \(N\) に対してもこれが成り立つと予想すると，「色の列を乱択して『解として相応しいかどうか』を確認してから出力する（相応しくなければやり直す）」という解法が考えられ，実際にこの方法で AC を得ることができます．

また，実験に思い至らなくても，「この問題のジャッジはどうなっているんだ？」と考えることでも思い付くことが可能かもしれません．

実装例 (C, 57 ms)

ジャッジ（解として相応しいかどうかの判定）

まず，この問題のジャッジについて考えてみます． 色の列 \(S\) が与えられたとき，操作後に色の列が \(S\) となるような色の列 \(T\) が存在するかどうかを判定したいです． この問題は \(N\) 変数 \(3N\) 節の 2-SATに帰着でき，これは \(2N\) 頂点 \(6N\) 辺の有向グラフの強連結成分分解に帰着できるので，\(\mathrm{O}(N)\) 時間で解くことができます．

文字列 \(R\) の \(i\) 文字目（色の列 \(R\) に関する頂点 \(i\) の色に対応する文字）を \(R[i]\) で表します． 変数 \(t_i \ (i = 1, 2, \dots, N)\) を，値が true であれば \(T[i] = {}\)B，値が false であれば \(T[i] = {}\)W を意味するものとして用意します． 頂点 \(i\) の隣接頂点を \(a, b, c\) とします． \(S[i] = {}\)B であれば，\(T[a], T[b], T[c]\) のうち少なくとも \(2\) 個が B である必要がありますが，これは

\[(t_a \vee t_b) \wedge (t_b \vee t_c) \wedge (t_c \vee t_a)\]

という制約で表現できます． これらの節は，「どれか \(1\) つでも false であれば，残り \(2\) つは必ず true である」という条件を表しており，これは「過半数が true である」ことと同値です． \(S[i] = {}\)W であれば，全ての変数を否定した節を用意すればよく，2-SAT への帰着が完了しました．

解として相応しい色の列の割合

この問題において，解として相応しい色の列の割合は十分大きいです． 実験的には，\(N = 6\) のときに \(\displaystyle\frac{30}{64} = 0.48675\) となるのが最小で， \(N \ge 12\) で少なくとも \(\displaystyle\frac{3}{5}\) 以上，\(N \ge 20\) で少なくとも \(\displaystyle\frac{4}{5}\) 以上が解として相応しく，この割合は \(N\) に関して増加傾向にあることが確認できます．

理論的には，補足で述べるように，「 \(N\) が大きいとき，およそ \(\displaystyle\frac{3}{4}\) 以上の色の列が解として相応しい」ことが証明できます． 具体的には，\(n = \left\lceil\displaystyle\frac{N}{46}\right\rceil\) に対して，

\[\frac{3}{16} \sum_{k = 1}^{n} \left(\frac{3}{4}\right)^{k-1} = \frac{3}{4}\left(1 - \left(\frac{3}{4}\right)^n\right)\]

以上であり，\(n \ge 10 \ (N \ge 416)\) で \(0.707\) 以上，\(n \ge 20 \ (N \ge 876)\) で \(0.747\) 以上となります．

成功確率の見積り

時間内に全てのテストケースに関して正答を得られる確率を考えます．（こちらも詳細は補足を参照．） 簡単のため，\(N\) が大きい場合のみからなる入力と，\(N\) が小さい場合のみからなる入力について考えます． （それらが混ざった入力に関しては，大きいもののみと小さいもののみでそれぞれ \(N\) の総和が \(5 \times 10^4\) 程度ある入力を考えるとこれで押さえられるので，時間に \(2\) 倍程度の余裕を見て確率を評価しておけばよいです．）

$N$ が大きい場合

まず，\(N\) が大きい場合について考えます． \(N \ge 416\) の場合，前述の解の割合から，一様乱択して失敗する確率は高々 \(0.293\) です． たとえば（余裕を持って）最大ケースに \(25\) 回連続で失敗した場合に TLE になると仮定すると，そのような確率は高々 \(0.293^{25} < 5 \times 10^{-14}\) です． \(N \ge 416\) を満たすテストケースは各入力に高々 \(\displaystyle\frac{5 \times 10^4}{416} \approx 120\) 個しかなく，入力が \(100\) 個あったとしても合計 \(1.2 \times 10^4\) 個程度です． それらのうち少なくとも \(1\) つに対して \(25\) 回連続で失敗する確率は，Union-Bound より，高々

\[5 \times 10^{-14} \times 1.2 \times 10^4 = 6 \times 10^{-10}\]

程度であり，このように \(N\) が大きいテストケースのみからなる場合には，十分高い確率で AC を得ることができます． （実際には，各入力内で平均的に早く成功すれば十分であり，解の割合の評価の緩さも併せると，この評価よりも遥かに高い確率で成功します．）

$N$ が小さい場合

次に，\(N\) が小さい場合について考えます． \(N \le 46\) の場合，前述の解の割合の理論的な下界は \(\displaystyle\frac{3}{16}\) であり，テストケースの数も多くなり得るので，\(N\) が大きい場合と同様の評価では心許ないかもしれません． 別の方法を考えてみましょう．

\(1\) つの入力における \(N\) の総和は \(5 \times 10^4\) 以下であり，最大の場合を考えれば十分です． \(N < 416\) の場合，テストケースは \(\displaystyle\frac{5 \times 10^4}{416} \approx 120\) 個以上あることになり，大数の法則から，実行時間の総和がその期待値から大きく外れる確率は非常に低くなります． 各テストケースに対する実行時間の期待値は，成功確率を \(p\) として定数倍を無視すると \(\displaystyle\frac{N}{p}\) であり，期待値の線形性から，全体の実行時間の期待値はこの総和となります． \(p\) は前述の通り \(N\) が小さくても \(\displaystyle\frac{3}{16}\) 以上（実験的には \(0.48\) 以上）であるので，\(\displaystyle\frac{1}{p}\) も十分小さい定数と考えることができ，直観的にはこれで十分です． 補足では，集中不等式を用いたより厳密な評価の一例を示します． （もっと良い方法があるかもしれません．）