AtCoder Regular Contest 150 A問題 Continuous 1

${\tt 0}, {\tt 1}, {\tt ?}$ からなる文字列 $S$ が与えられる. $S$ にある全ての ${\tt ?}$ をそれぞれ ${\tt 0}$ または ${\tt 1}$ に置き換える方法で, 以下の条件を満たすものは唯一存在するか?

$T$ ケースのマルチケース

条件を満たすような完成後の文字列は連続する区間と1対1に対応する. よって, 長さ $K$ の連続部分区間それぞれにおいて, その区間にのみ ${\tt 1}$ を並べることができることが可能かどうかを判定し. 可能である区間がちょうど1かどうかを答えれば良い.

長さ $K$ の連続部分区間の最初を第 $i$ 項目とする. このとき, 長さ $K$ の連続部分区間は $(i,i+1, \dots, i+K-1)$ である.

第 $i$ 項目を最初とする長さ $K$ の連続部分区間にのみに ${\tt 1}$ を並べ, それ以外は ${\tt 0}$ になるような ${\tt ?}$ への置き換えが存在することの必要十分条件は以下を共に満たすことである.

(証明)

(十分性)
第 $i$ 項目を最初とする長さ $K$ の連続部分区間にのみに ${\tt 1}$ を並べる置き換えが可能なとき, ${\tt ?}$ の置き換えは第 $i$ 項目から第 $(i+K-1)$ 項目までは ${\tt 1}$ へ, それ以外は ${\tt 0}$ への置き換えが唯一である. このとき, $S\_i, S\_{i+1}, \dots, S\_{i+K-1}$ の中に ${\tt 0}$ が存在すると, 目標としている区間に ${\tt 1}$ が $K$ 個連続しない. また, $S\_i, S\_{i+1}, \dots, S\_{i+K-1}$ 以外に ${\tt 1}$ すると, 目標としている区間に ${\tt 1}$ が $K$ 個並んでいる場合, 全体として ${\tt 1}$ が $K$ 個より多くなってしまう.
(必要性)
第 $i$ 項目を最初とする長さ $K$ の連続部分区間にのみに ${\tt 1}$ を並べる置き換えを目指す場合, ${\tt ?}$ の置き換えは第 $i$ 項目から第 $(i+K-1)$ 項目までは ${\tt 1}$ へ, それ以外は ${\tt 0}$ への置き換えなくてはならない. $S_i, \dots, S_{i+K-1}$ にあるのは ${\tt 1}, {\tt ?}$ に限られるので, 置き換え後はこれらは全て ${\tt 1}$ になる. そして, それ以外には ${tt 0}, {\tt ?}$ しかないので, 置き換え後は全て ${\tt 0}$ になる.