盤面の色と \(s\) から、ゲーム終了時の黒い石の個数を求める方法

両端のマスが同じ色だったら、その色が \(n\) 個になる。 そうでない場合、端にある黒マスの連結成分を \(S_B\)、逆側の端にある白マスの連結成分を \(S_W\) と呼ことにすると、

• \(s\) から見て、 \(S_B\) よりも \(S_W\) への距離のほうが小さい場合、黒い石は \(|S_B|\) 個になる
• そうで無い場合、黒い石は \(n-|S_W|\) 個になる

理由

盤面上で、白い石は絶対に連結になるし、黒い石も絶対に連結になることが示せる。 また、両端の石の色は置かれたときから変わることはない。 よって、両端が同じ色だったら、全部その色になるはずである。

両端のマスの色が異なる場合を考える。\(S_W, S_B\) のどちらに先に石が置かれたかで場合分けをする。\(S_B\) に置かれた場合、その後 \(S_W\) に石が置かれる直前には、置かれてる石の両端がどちらも黒であるため、先程の議論と同様に盤面の石はすべて黒であることがわかる。よってこれ以降すでに置かれている石の色が変更されることは無く、最終的な黒い石の数は \(n-|S_W|\) 個になる。\(S_B\) に置かれた場合、同様に最終的な黒い石の数は \(|S_B|\) 個になる。よって、黒石さんは \(S_B\) めがけて石を置き続けるし、白石さんは \(S_W\) めがけて石を置き続けるため、先述の通り \(S_B\) と \(S_W\) への距離によって結果が決まる。

数え上げ

白い石の個数の期待値を \(W\) として、黒い石の個数の期待値を \(B\) とすると、\(W+B=n\)である。 このことから、\(W-B\)が求まれば\(W\)も求まる。

ここで、盤面の白黒を反転させると結果がどう変わるかを考える。 「ほとんど」の場合は、黒い石の残る個数が \(x\) 個であるゲームを反転させると、白い石の残る個数が \(x\) 個であるゲームになる。よって、このようなケースは \(W-B\) を考える場合は打ち消されるため、考えなくて良い。

「ほとんど」に該当しないケースは、 \(s\) から見て、 \(S_B\) への距離と \(S_W\) への距離が等しい場合だけである。

\(S_B\) が左側にあり、 \(s\) が半分より左にある場合を考える。このとき、最終的な黒い石の個数と白い石の個数の差は \(4s-2|S_B|-n+2\) 個であり、確率は \(2^{-n+2s-2|S_B|-1}\) である。よって、\((4s-2|S_B|-n+2)2^{-n+2s-2|S_B|-1}\) の \(|S_B| = 1,2,\dots,s-1\) の場合についての和が高速に計算できれば良い。 この和は \( \Sigma_{i=0}^k (a+bi) 4^i\) という形をしている。

\(S_B\) が左側にあり、 \(s\) が半分より右にある場合を考える。このとき、最終的な黒い石の個数と白い石の個数の差は \(n-2|S_W|\) 個であり、確率は \(2^{n-2s-2|S_W|-3}\) である。よって、\((n-2|S_W|)2^{n-2s-2|S_W|-3}\) の \(|S_W| = 1,2,\dots,n-c-2\) の場合についての和が高速に計算できれば良い。 この和も \( \Sigma_{i=0}^k (a+bi) 4^i\) という形をしている。

他の場合もこれらと同様である。よって、この式を効率よく計算できればよい。

これは、\( \Sigma_{i=0}^k 4^i\) と \( \Sigma_{i=0}^k i4^i\) のそれぞれを \(O(n)\) で各\(k=0,\dots,n\) について前計算しておいて、適切な係数をかけて足すと計算できる。 もしくは、\( \Sigma_{i=0}^k i4^i\) を\(\Sigma_{i=1}^k 4^i \Sigma_{j=0}^{k-i} d^j\) のように変形して、等比数列の和の公式を用いて式変形することにより、\(O(\log k)\) で計算することもできる。

C++による実装 （解説では期待値を直接計算していますが、この実装では個数を数えた後に割り算しています。）