Ex - Dye Color Editorial
by 
Nyaan
ユーザー解説です。
別解：色ごとに独立したマルコフ連鎖とみなす考え方
想定解は少し ad-hoc に感じられる面があると思います。
解法に至るまでの別の道筋として、操作を色ごとに独立したマルコフ連鎖(ある種のランダムウォーク)として捉える方法もあります。どちらの解法でも結果として得られる式は一致します。
1つの色に注目すると、その色で塗られたボールの個数がある遷移行列に従って独立に変化しているのを利用します。
- 最終的に色 \(i\) ですべて塗られる確率を \(P_i\)
- 最終的に色 \(i\) で塗られる場合において、停止するまでにかかる回数の条件付き期待値を \(F_i\)
とします。求めたい答え \(S\) は \(P,F\) を用いて \(S = \sum_i P_i F_i\) と表せます。また \(\sum_i P_i = 1\) です。
また、 \(g(x)\) を次のように定義します。
- \(x\) 個のボールに色 \(i\) が塗られている状態から始めて、停止条件を無視して色を塗り替え続けたときにすべて色 \(i\) に塗られるまでの回数の期待値を \(g(x)\) とおく。
元の問題で、はじめに色 \(i\) に塗られたボールの個数を \(c_i\) とします。\(g(c_i)\) は「元の問題のはじめの状態から、停止条件を無視して操作を行って色 \(i\) ですべて塗られるまでの回数の期待値」と一致します。(色 \(i\) で塗られたボールの個数が他の色の変化にかかわらず独立に変化する性質から従います。)よって、元の問題の状況を踏まえると \(g(c_i)\) は
- \(g(c_i) = \sum_{j} P_j\) (元の問題のはじめの状態からスタートして、はじめに 色 \(j\) ですべて塗られた後、そこから色 \(i\) ですべて塗られるまでにかかる回数の期待値)
と表せます。カッコ内は \(i = j\) のとき \(F_i\) 、\(i \neq j\) のとき \(F_j + g(0)\) です。 \(F_i\) を含む項を左辺に移項して
\[P_i F_i = g(c_i) - \sum_{j\neq i} P_i \left(F_j + g(0)\right)\]
を得ます。\(i\) について総和を取って適切に変形すると
\[S = \sum_i (g(c_i)/N) - (N-1) (g(0)/N)\]
を得ます。この \(g(i)/N\) は公式解説が計算している \(g(0), g(1), ..., g(N-1)\) に定数を加えたものと一致していて \(\mathrm{O}(N^2)\) 程度で計算できるので、この問題を解くことができました。
ポテンシャル関数
公式解説にある \(g(i)\) のような関数はしばしばポテンシャル関数と呼ばれています。ここではポテンシャル関数が存在する条件の一般化を試みました(があまりうまくいってない気も…)。乱文失礼します。
まず、次のような問題を考えます。
- 状態 \(1\), 状態 \(2\), \(\dots\) ,状態 \(N+M\) の \(N+M\) ヵ所の状態がある。
- 状態 \(i\) \((1 \leq i \leq N)\) にいるとき \(p_{i,j}\) の確率で状態 \(j\) に移動する。(移動はランダムかつ独立)
- 状態 \(N+1,N+2,\dots,N+M\) のいずれかに着いたら移動をやめる(停止状態になる。)
- \(1 \leq i \leq N\) を満たす全ての \(i\) について、状態 \(i\) をスタートして移動し続ければいつかは状態 \(N+1,N+2,\dots,N+M\) のいずれかに辿り着ける。
- \(1 \leq s \leq N\) について、状態 \(s\) にいる状態からスタートして、移動を停止するまでに移動する回数の期待値を求めたい。
ゴールにたどり着くまでの期待値の求め方
行列 \(P\) を \(P_{i,j}=p_{i,j}\) を満たすような \(N \times N\) 行列とする。 このとき、\(E(i)\) を 「状態 i にいる状態から始めて 状態 N に行くまでの移動回数の期待値」とすると次の式が成り立つ。
\[ \left( \begin{array}{c} E(1) \\ E(2) \\ \vdots \\ E(N) \end{array} \right) = P \left( \begin{array}{c} E(1) \\ E(2) \\ \vdots \\ E(N) \end{array} \right) + \left( \begin{array}{c} 1 \\ 1 \\ \vdots \\ 1 \end{array} \right) \]
これはゴールが存在するマルコフ連鎖に関する広く知られたテクニックです。(「蟻本」にも載っていています。)
この事実を利用すれば、 \(N\) が小さい場合は連立方程式の解を \(\mathrm{O}(N^3)\) で求めることで十分高速に解くことができます。
- これは余談ですが、行列 \(P\) の性質が良いことを利用して \(\mathrm{O}(N^2)\) や \(\mathrm{O}(N \log N)\) で解を計算させる問題も各所で何問か出題されています。
次に、ポテンシャル関数 と呼ばれるものを以下のように定義します。
ポテンシャル関数
ポテンシャル関数 \(f(i)\) \((i=1,2,\dots,N+M)\) を次の式を満たすように定義します。
- \(1 \leq i \leq N\) について \(\displaystyle f(i) = 1 + \sum_{1 \leq j \leq N+M} p(i,j) f(j)\)
- 停止状態のポテンシャルが一定である。すなわち \(f(N+1) = f(N + 2) = \dots = f(N + M)\) である。
このとき、状態 \(i\) から停止状態になるまでの移動回数の期待値は、停止状態のポテンシャルを \(C\) として \(f(i) - C\) となる。
正当性は \(f(i)\) の式を行列で表すと確認できます。より厳密には \(E(i)\) は \(f(i)\) に定数 \(C\) を足したものになります。
ポテンシャル関数は停止時刻の期待値をより一般化した量になっています。
元の問題が以下に説明するよりよい性質を持っていた場合、ポテンシャル関数をいくつかの小問題のポテンシャル関数の和で表すことができます。
ポテンシャル関数の分割
元の問題がいくつかの小問題の重ね合わせで解釈できるとする。すなわち、状態 \(1'\), 状態 \(2'\), \(\dots\) 状態 \((L+K)'\) があって、状態 \(i\) がいくつかの状態からなる多重集合 \(s_i = \lbrace a'_{i,1},a'_{i,2},\dots,a'_{i,k} \rbrace\) で表せるとする。
また、小問題それ自体も同様の構造(吸収マルコフ連鎖)を持っているとする。すなわち、ある \(L \times (L+K)\) 行列 \(Q\) が存在して、状態 \(a'_{i}\) は 1 回の移動のあとに状態 \(a'_{j}\) に \(Q_{i,j}\) の確率で独立ランダムに移動する。また、いずれかの小問題の状態が状態 \((L+1)', \dots, (L+K)'\) に到達したあとは移動は発生しない。
さらに、ある関数 \(h\) が存在して、すべての元の問題の停止していない状態 \(i\) \((1 \leq i \leq N)\) に対して\[\sum_{t \in s_i} h(t) = 1\]
が成り立っているとする。
このとき、
\[ \left( \begin{array}{c} g(1') \\ g(2') \\ \vdots \\ g(L') \end{array} \right) = Q \left( \begin{array}{c} g(1') \\ g(2') \\ \vdots \\ g((L+K)') \end{array} \right) + \left( \begin{array}{c} h(1') \\ h(2') \\ \vdots \\ h(L') \end{array} \right) \]
かつ
\[\sum_{t \in s_{N+1}} g(t) = \sum_{t \in s_{N+2}} g(t) = \dots = \sum_{t \in s_{N+M}} g(t)\]
を満たすような \(g\) が存在すれば、
\[f(i) = \sum_{t \in s_{i}} g(t)\]
を満たす \(f(i)\) は元の問題のポテンシャル関数として条件を満たす。また、元の問題の状態 \(i\) から停止状態に至るまでの移動回数は
\[\sum_{t \in s_{i}} g(t) - \sum_{t \in s_{N+1}} g(t)\]
になる。
正当性は頑張って式変形をすれば示せると思います。
このように問題を分割することで \(g(1'), g(2'), \dots, g((L+K)')\) を計算できれば問題を解くことができます。よって元の問題に比べて小問題の状態数が十分少なければ計算量を改善することができます。
なお、上記の議論はすべて実数の世界で成り立っている点に注意が必要です。\(\text{mod }P\) の世界ではこれに加えて \(\text{mod }P\) 上で表現可能な \(g(1'), g(2'), \dots, g((L+K)')\) が存在するか (求める過程で \(0\) 割りが発生しないか) を証明する必要があります。
出題例
上記のテクニックをそのまま適用できる問題は CodeForces の Div 1 を中心に何問か出題されています。演習用にお使いください。
(ネタバレ防止用に畳んでいます)
posted:
last update: