解説で飛ばした証明の補足です．

$N$ が大きいとき，およそ $\displaystyle\frac{3}{4}$ 以上の色の列が解として相応しい

\(N\) 頂点から，互いの距離が \(5\) 以上となるように \(n\) 頂点 \(r_1, r_2, \dots, r_n\) を選びます． 次数の制約から，ある頂点から距離が \(4\) 以下の頂点は高々 \(3 + 6 + 12 + 24 = 45\) 個しかないので，\(n \ge \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\) 以上となります．

色の列を頂点とし，操作による遷移を有向辺で表した有向グラフを考えると，解として相応しい色の列は「入次数が \(0\) の頂点」に対応します． この有向グラフでは，各頂点からちょうど \(1\) 本の辺が出るため，その辺数は頂点数と等しいです． したがって，入次数が \(0\) の頂点の個数は，「入次数が \(1\) 以上の頂点に関して，入次数から \(1\) を引いた値」の総和に等しいです． 後者は「操作によって同じ色の列に遷移するような色の列の個数から \(1\) を引いた値」の総和となります． 以上の観察から，解として相応しい色の列を数える代わりに，操作によって同じ色の列に遷移するような色の列の組 \((S, S')\) を，閉路ができないように（ \((S, S')\) を辺と見なした無向グラフが森となるように）なるべくたくさん数えることにします．

\(k = 1, 2, \dots, n\) に対して，以下のように組を作って数えます． まず，\(r_k\) の隣接頂点を \(a_k, b_k, c_k\) とし，

• \(S[a_k] = S[b_k] = S[c_k]\)
• 各 \(j = 1, 2, \dots, k -1\) について \(S[a_j] \neq S[b_j]\) または \(S[b_j] \neq S[c_j]\) または \(S[c_j] \neq S[a_j]\)

がともに成り立つような色の列 \(S\) を考えます． ここで，\(r_k\) 達の距離が互いに \(5\) 以上であることから，上記の条件は全て独立に考えることができ，このような色の列は全体の \(\left(\displaystyle\frac{1}{4}\right)\left(\displaystyle\frac{3}{4}\right)^{k-1}\) だけあります． さらに，\(1\) つ目と \(2\) つ目の条件から，異なる \(k\) に関して \(S\) として重複する色の列はありません．

このような色の列 \(S\) に対して，\(a_k, b_k, c_k\) のうち \(1\) つを選んでその色のみを反転した色の列を \(S'\) とします． このとき，\(S\) と \(S'\) に対して操作を行った結果が同じとなるような組 \((S, S')\) がいくつあるかを考えます． ここで，いずれの場合も \(S[a_k] = S[b_k] = S[c_k]\) の状態から \(S'[a_k] \neq S'[b_k]\) または \(S'[b_k] \neq S'[c_k]\) または \(S'[c_k] \neq S'[a_k]\) の状態になることと，\(2\) つ目の条件（ \(j < k\) に関するもの）から，このようにして得られる組 \((S, S')\) を \(k\) を動かして全て数えても閉路ができることはありません．（各 \(S\) について，等号条件が成り立つ最小の \(k\) のみが崩れる方向に組の相手 \(S'\) を持つため，組を辿って到達可能な色の列の対があるとき，その間の経路は常に一意に定まります．）

対称性から，\(S'[a_k] \neq S[a_k]\) の場合を考えて結果を \(3\) 倍します． \(a_k\) の隣接頂点のうち，\(r_k\) でないものを \(x, y\) とします． \(S\) と \(S'\) に対して操作を行った結果が同じになるということは，\(x, y\) の隣接頂点のうち \(a_k\) でないものに塗られた色がそれぞれ同じである（操作後に \(x, y\) の色がそれぞれその色となる）ことと同値です． \(x, y\) とその隣接頂点は \(r_k, b_k, c_k\) のいずれかと一致する可能性がありますが，\(r_j, a_j, b_j, c_j \ (j \neq k)\) と一致することはありません．（ \(r_k\) と \(r_j\) の距離が \(5\) 以上であることを思い出しましょう．） したがって，そのような条件を満たす \(S\) の割合は，上記の条件下で少なくとも \(\left(\displaystyle\frac{1}{2}\right)^2 = \displaystyle\frac{1}{4}\) 以上であることが確認でき，結果として全体の \(\left(\displaystyle\frac{1}{4}\right)^2\left(\displaystyle\frac{3}{4}\right)^{k-1}\) の色の列 \(S\) について \(S'\) と操作後の色の列が一致することが従います． これを \(3\) 倍して \(k\) に関して足し合わせることで，冒頭の結果を得ることができました．

$N$ が小さいテストケースのみからなる入力に対する成功確率の見積り

有名な集中不等式として，以下の Chernoff bound を用います．

\(X\) を確率変数とし，\(a, t\) を正の実数とする．このとき，以下の不等式が成り立つ．

\[\mathrm{Pr}(X \le s) \le e^{ts} \cdot \mathbf{E}[e^{-tX}]\]

\(N \le 416\) のテストケースのみからなる入力について考えます． \(1\) つの入力における \(N\) の総和は \(5 \times 10^4\) 以下であり，最大の場合を考えれば十分です． さらに，簡単のため，全てのテストケースについて \(N\) の値が同じである場合，すなわち \(T \approx \displaystyle\frac{5 \times 10^4}{N} \ge 120\) の場合を考えます． （そうでない場合は，たとえば \(N\) の値を適当な幅で区切って，範囲 \([N_\mathrm{min}, N_\mathrm{max}]\) ごとに \(N_\mathrm{max}\) が \(\displaystyle\frac{5 \times 10^4}{N_\mathrm{min}}\) 個ある場合を考えるなど，多少悪くなるように評価しても大丈夫な程度には余裕があります．）

成功確率を \(p\)，失敗確率を \(q = 1 - p\) とし，定数倍を無視して \(1\) 回の試行の実行時間を \(N\) として，入力テストケース全体に掛かる実行時間がある程度より大きくなってしまう確率を見積もります． \(1\) つのテストケースに対して成功するまでの試行回数の期待値は

\[\sum_{k = 1}^\infty pq^{k-1} kN = \frac{pN}{1 - q}\left(\sum_{k = 1}^\infty kq^{k-1} - \sum_{k=1}^\infty kq^k\right) = N\sum_{k=0}^\infty q^k = \frac{N}{p}\]

なので，期待値の線形性から，入力全体の計算時間の期待値は \(\displaystyle\frac{TN}{p}\) です． そこで，\(a > \displaystyle\frac{1}{p}\) を満たす実数 \(a\) を適当に選んで，入力全体に対して合計 \(aT\) 回の試行を行ったとし，その時点での成功回数が \(T\) 回未満となっている確率を評価します．

\(i\) 回目の試行が成功であれば \(1\)，失敗であれば \(0\) の値を取る確率変数を \(X_i \ (i = 1, 2, \dots, aT)\) とすると，成功回数は \(X = X_1 + X_2 + \cdots + X_{aT}\) です． このとき，

\[\mathbf{E}[e^{-tX_i}] = pe^{-t} + q\]

であり，\(X_1, X_2, \dots, X_{aT}\) は独立なので，

\[\mathbf{E}[e^{-tX}] = \mathbf{E}\left[e^{-t\sum_{i=1}^{aT} X_i}\right] = \mathbf{E}\left[\prod_{i=1}^{aT} e^{-tX_i}\right] = \prod_{i=1}^{aT} \mathbf{E}[e^{-tX_i}] = \left(pe^{-t} + q\right)^{aT}\]

が成り立ちます．

このとき，前述の Chernoff bound を適用してみると，

\[\mathrm{Pr}(X < T) \le \mathrm{Pr}(X \le T) \le e^{tT} \left(pe^{-t} + q\right)^{aT}\]

が得られます． 不等式の右辺は小さいほど嬉しいので，最小値を達成する \(t\) を考えてみましょう．

不等式の右辺を \(f(t)\) とおくと，

\[\log f(t) = tT + aT\cdot \log \left(pe^{-t} + q\right)\]

であり，これを \(t\) で微分すると

\[\frac{\mathrm{d}}{\mathrm{d}t}\log f(t) = T + aT\cdot\frac{-pe^{-t}}{pe^{-t} + q}\]

となります． この右辺は \(t \to +0\) で \(T - apT < 0\)，\(t \to +\infty\) で \(T > 0\) に収束し，

\[pe^{-t^*} = \frac{q}{a-1}\]

を満たす \(t^*\) でのみ \(0\) になります． したがって，この \(t^*\) が \(f(t)\) の最小値を達成し，その最小値は

\[f(t^*) = \left(\frac{p}{q}\cdot(a - 1)\right)^T\left(q\cdot\left(1 + \frac{1}{a-1}\right)\right)^{aT} = \left(pq^{a-1}a\cdot\left(1 + \frac{1}{a-1}\right)^{a-1}\right)^T\]

となります．

\(p = \displaystyle\frac{3}{16}, \ q = 1 - p = \displaystyle\frac{13}{16}\) のとき，たとえば \(a = 10\) とすると \(T\) 乗の中身はおよそ \(\displaystyle\frac{3}{4}\) となり，\(T = 120\) のとき全体の値は \(10^{-15}\) 程度です． したがって，\(N\) が小さいテストケースのみからなる最大の入力について，試行回数が \(10T\) 回を超える（平均的に \(10\) 回以上ずつ失敗する）確率はほぼゼロであり，余裕を持って時間内に AC を得ることができます．