Codeforces Round #668 (Div. 2) C. Balanced Bitstring

気づき

インデックス mod K で一致する
範囲内で片方が $\frac{K}{2}$ より多く存在したら不適

1.について
問題を眺めていても閃かないので、この手の問題の常套手段をまず確認する。

具体的に手を動かす
抽象的に手を動かす
前から操作する
後ろから操作する
操作しても変わらない箇所（単位元）を探す
2回操作すると、もとに戻る操作（逆元）を探す

他にもあるだろうけど、まずはこれだけ確認しておく。

この問題については、「1」「2」「5（の亜種）」がヒントとなる。
1.はサンプルなどを具体的に操作して問題を理解するだけなので、スルー。

2.、5.について、fig.1のように考えると、
与えられる文字列を $S$ 、 $S$ の $i$ 文字目を $S_i$ 、範囲の長さを $K$ として、
$S_i$ と $S_{i+K}$ は等しくなければならないとわかる。
よって、任意の $i,j$ について、 $S_{i\%K} = S_{j\%K}$ が要求される。
ここでこの気付きを、5.（の亜種）としたのは、範囲を一つずらしたとき、長さ $K-2$ の共通部分があり、その範囲内の0と1の数は変わらないので、共通部分の左右は同じ値になる、という、変化しない共通部分を見つけていることに対応する。

これらの事実より、 $S_{i\%K} = S_{j\%K}$ が成り立たない場合、その時点で不適。
また、 $S_{i\%K} = S_{j\%K}$ が成り立たないといけないので、 $\mod K$ が等しいインデックスの中に「 $?$ 」と「 $1$ または $0$ 」が存在すると、 $?$ は $0$ 、 $1$ どちらかに決定する。
これらの操作をすると、 $S_{i\%K} = S_{j\%K}$ が常に成り立つ状態になるので、始点 $0$ から $K-1$ に対して、含まれる $0$ の数が $\frac{K}{2}$ より大きくないかチェックすればOK。
（ $\because$ $0$ が $\frac{K}{2}$ より多い場合、含まれる $?$ をすべて $1$ にしても不適だから）
始点 $0$ から $K-1$ だけチェックすれば大丈夫なのは、具体的にコードを書いてみるとわかるが、 $a=vec[vec[$ ;K]]という配列をとって、
a[i%K].push(S[i])
と追加して、 $?$ を決定する操作をすると、任意 $i,j$ について $a_i=a_j$ となるので、 $a_0$ の範囲で始点を試せば、あとは同じチェックになる。