ゲーム中に、次の二つの値を保持しておきましょう。

• \(L\): すぬけ君の左側に連続する空マスの数（左側の一番近いブロックまで）
• \(R\): すぬけ君の右側に連続する空マスの数（右側の一番近いブロックまで）

すぬけ君はこれらの \(L + R + 1\) マスから脱出できないため、この二つの値のみが意味を持ちます。また、\(a \leq a'\) かつ \(b \leq b'\) であれば、すぬけ君にとって状態 \((a', b')\) は状態 \((a, b)\) より悪くはないことに注意します（厳密な証明は、残りステップ数に関する帰納法を用いることで可能です）。

したがって、ゲームは以下のようにシミュレートできます。

• 状態 \((\infty, \infty)\) から開始する。
• すぬけ君のターンでは、状態 \((L, R)\) を \((L+1, R-1)\) か \((L-1, R+1)\) に変換できる（しなくてもよい）。
• あなたのターンでは、状態 \((L, R)\) を \((0, \min \{ L, R \})\) に変える。

与えられたターン文字列に対して、どのように勝者を判定できるでしょうか。 例えば、ターン文字列が \(S...SBS...SBS...SBS...SBS...SBS...S\) であり、\(S\) が左から順に \(a, b, c, d, e, f\) 個連続しているとします。

• 最初の \(B\) のあと、状態は \((0, \infty)\) となります。
• その後、すぬけ君が状態を \((b, \infty)\) に変えます。
• 二個目の \(B\) のあと、状態は \((0, b)\) となります。
• その後、すぬけ君は \(x = \min \{ [b/2], c \}\) として状態を \((x, b-x)\) に変えるのが最適です。

このような観察を繰り返すことで、すぬけ君が勝利する必要十分条件は \( \min \{ [b/8], [c/4], [d/2], e \} \geq 1\)、すなわち \(b \geq 8, c \geq 4, d \geq 2, e \geq 1\) であることがわかります。

ここから、\(O(N \log N)\) の DP による元の問題の解法が得られます。