初期状態から変化していないマスを = で、左向きの足跡で書き換えられたマスを < で、右向きの足跡で書き換えられたマスを > で表すと、最終状態は <<..<==..=>>..> のようになります。 つまり、< で書き換えられたマスの左のマスも < で書き換えられ、> で書き換えられたマスの右のマスも > で書き換えられます。 また、 = の区間としてありうるのは、初期状態で . を含まない極大な区間のみです。 よって、ありうる最終状態は、穴の空いているマスの数を \(k\) としたとき、 \(k+1\) 個しかありません。 それぞれの最終状態になる確率を求めればこの問題を解くことができます。

初期状態で左から \(d\) 個の . のマスが < で書き換えられ、残りの \(k-d\) 個の . のマスが > で書き換えられる操作方法の数を考えます。 左の \(d\) 個の . に対する操作と、右の \(t-d\) 個の . に対する操作は、互いに影響を与えません。 よって、左側に対する条件を満たす操作方法の数 \(L_d\) と、右側に対する条件を満たす操作方法の数 \(R_{t-d}\) を求めれば、\(L_dR_{t-d} \binom{k}{d}\) が求める数になります。

\(L_0,\dots,L_k\) を求めるために、最終的に < で書き換えられるマス以外を消して考えます。 \(i\) 番目のマスを埋めたあとにすぬけくんが向く向きに注目します。 \(i\) 番目のマスを埋めた時点で \(i\) マス目の右に穴の空いたマスがあるとき、すぬけくんが向く方向は最終状態に影響を与えません。 初期状態で足跡がついているマスについても同様です。 なぜなら、すぐ右にある穴の空いたマスが < になったときに \(i\) マス目も < となるためです。 逆に、 \(i\) マス目の右に穴の空いたマスがなければ、すぬけくんは必ず左を向く必要があります。

この考察を使って \(L_0,\dots,L_k\) についての漸化式をたてます。 \(d+1\) 個の . が < で書き換えられるとして、一番左の穴の空いたマスを何番目にうめるかで場合分けをします。 \(d+1\) 番目である場合は必ず左を向く必要があり、それ以外の場合はどちらを向いても良いです。 残りの \(d\) 個の空きマスの相対的な順番と向きの決め方は \(L_d\) 通りなので、\(L_{d+1}=(2d-1)L_d\) です。

また、操作の左右を入れ替えることで、\(L_d = R_d\) であることが分かります。

C++による実装例