Codeforces Round #573 (Div. 1) C. Tokitsukaze and Duel

問題概要

0または1からなる $n$ 文字の文字列 $S$ と整数 $k$ が与えられ、それを用いて2人がゲームをする。交互にターンが回り、それぞれのターンで各プレイヤーは「連続する $k$ 文字を選び、それらを全て0または全て1にする」という操作を行う。プレイヤーの操作後に全ての文字が同じになったとき、そのプレイヤーが勝利する。

2人が最適に行動した時に先攻と後攻のどちらが勝つか、または $10^{9}$ ターン経過しても決着が付かない（引き分け）か、判定せよ。

制約

$1 \le k \le n \le 10^{5}$
$S$ は0または1からなる $n$ 文字の文字列

解法

ゲームの展開を以下のように分類しましょう。

パターン1：先攻が1ターン目で勝つ場合

入力例3のようなケースです。あるいはもっと分かりやすい例だと、

8 4
01111000

などが該当します。4個並んでいる1を全て0に変えると勝ちです。

先攻が1ターン目で勝てるかどうかの判定は次のようにできます。左端から連続して0が並んでいる個数を $L_{0}$ 、右端から連続して0が並んでいる個数を $R_{0}$ として、もし $L_{0} + k + R_{0} \ge n$ であれば間を0に変えることで勝てます。同様に1についても判定できます。

このように、次に1回操作することで勝てるような文字列の状態を「リーチ状態」と呼ぶことにします。

※既に全文字が一致している場合も「リーチ状態」に含めます。テストケース5～8などにあるように、これが初期状態として与えられた場合も先攻の勝ちになります。

パターン2：後攻が1ターン目で勝つ場合

入力例1のようなケースです。

4 2
0101

入力例1では、先攻1ターン目では勝てません。そして先攻が操作した後の文字列として考えられるものは 0001 0100 1101 0111 です。これらは全てリーチ状態であり、どれを渡しても後攻が次の操作で勝つことができてしまいます。

もし操作後の文字列でリーチ状態でないものが1つでもあれば、先攻はそれを渡すことでひとまず負けを免れます。つまり「先攻が1ターン目で勝てないとき、後攻が1ターン目に勝てるかどうか？」は、「先攻1ターン目の操作の結果として考えられるもの全てがリーチ状態であるか？」と言い換えられます。これを調べるために、「先攻が操作する場所」×「0にするか1にするか」を全探索しましょう。

先攻の操作が0に変更するものだったとすると、判定に必要な情報は先ほどと同じく、先攻の操作後に左右端からそれぞれいくつ0が連続で並んでいるかの値です。これを先ほどと同じく $L_{0}, R_{0}$ と表記します（これらは操作位置に依存します）。これを任意の操作位置について高速に計算したいです。

これは前もって、全ての位置について「そこから左/右に連続で0がいくつ並んでいるか？」を調べておくことで可能です。この前計算は端から順番に見ていくことで $O(n)$ でできます。インデックス $i$ の位置から左に連続で0がいくつ並んでいるかを $l_{i, 0}$ 、右に連続で0がいくつ並んでいるかを $r_{i, 0}$ と表記します。

この情報を持っておけば、先攻が0に変更する区間を $\lbrack i, i+k-1\rbrack$ と決めた時に、左端から0が連続している個数 $L_{0}$ は

左端から操作位置まで0が繋がっていない場合、つまり $r_{1, 0} \lt i-1$ であるときには、単に元の状態のまま $L_{0} = r_{1, 0}$
左端から操作位置まで0が繋がっている場合、つまり $r_{1, 0} \ge i-1$ であるときには、操作位置のさらに右まで繋がるので $L_{0} = i+k-1+r_{i+k, 0}$

となります（1-indexedです）。

同様の方法で $R_{0}$ も計算することができて、 $L_{0} + k + R_{0} \ge n$ かどうかでリーチ状態であるかどうかを判定できます。これを1に変更する場合についても全部試して、先攻の全ての操作についてリーチ状態であれば後攻が勝ちです。

パターン3：それ以外の場合

それ以外の場合はどうなるでしょうか。これは実は必ず引き分けになります。

重要な性質として、「1回操作された後の文字列は、直前の相手の操作と全く同じ操作をすることで、文字列を変えないようにできる」ということが言えます。このことから、もし「不利な」文字列があったとして、それが相手から渡されてきた場合は、そっくりそのまま相手に返すことができます。これを永遠に繰り返して引き分けになります。

もう少しちゃんと書くと、後退解析の考え方を用います。

ゲームを解く！Educational DP Contest K, L 問題の解説 - Qiita

つまり、「自分の操作前にどうなっていれば勝ちか/負けか」観点で以下のように状態を分類します。