AtCoder Grand Contest 045 C - Range Set

解法

必要十分条件への言い換え

ある01文字列が与えられた時に、それが操作によって生成可能であるかを判定することを考えます。

ここで今回のように「塗り潰す」系の操作の場合、「判定したい文字列から逆順で操作を行い、初期状態に戻せるか？」と考えると見通しが良くなることが多いです。塗り潰す操作を逆に見ると「塗り潰す前は何でも良い」と思うことができるので、「何でも良い」領域をどんどん広げていくことで初期状態にマッチさせることを目指します。

具体的には、今回の問題における逆操作は

操作0：0 または * が $A$ 個連続している領域（混ざっていても良い）を、全て * に置き換える。
操作1：1 または * が $B$ 個連続している領域（混ざっていても良い）を、全て * に置き換える。

と記述することができます。ここで * は「0 と 1 のどちらでも良い」ことを意味します。

初期状態は全て 0 なので、判定したい文字列からこれらの操作を続けて 0 または * しか存在しない文字列にできれば生成可能ということになります。ただし 0 または * しか存在しない文字列はさらに操作0を繰り返すことで必ず全て * にできるので、条件を「全て * にできること」と言い換えても良いです。こうすると最後の条件において 0 1 の区別がなくなります。

さらに考えると、これは $\max(A, B)$ 個以上の連続する * を作ることができれば必ず達成可能であることが分かります。これが1箇所できてしまえば、あとはそれに隣接する1文字を * に変える操作が必ず可能で、文字を全て * に変えることができるからです。

最後の条件に 0 1 の区別がなくなったので、 $A \le B$ として解くことができます。もし $A \gt B$ である場合は生成可能な文字列の 0 1 を反転させると思うことでスワップすることができるからです。このときある01文字列が生成可能である必要十分条件は、

操作0、操作1の繰り返しによって、* が $B$ 個以上連続している領域を作ることができること。

です。操作1を1回行った時点で条件が満たされると考えると、これは

操作0の繰り返しによって、1 または * が $B$ 個以上連続している領域を作ることができること。

と言い換えることができて、* を 1 に置き換えてしまうと結局

連続する $A$ 個以上の 0 を全て 1 に置き換えた後、1 が $B$ 個以上連続している領域が存在していること。

とまで言い換えることができます。

数える

先ほどの必要十分条件を満たす01文字列を数えます。

もし $A$ 個以上の 0 を 1 に置き換える操作がなければ、次のようなDPで条件を満たさないものを数えることができます。

$dp\lbrack i \rbrack\lbrack j \rbrack =$ 前から $i$ 文字を決めて、直前の連続している 1 の個数が $j$ 個であって、これまでの遷移で $j \ge B$ となったことが一度もないような01文字列の個数

※余事象を考えていることはあまり本質ではなくて、例えば「一度でも 1 が $B$ 個以上連続したことがある」というフラグを足すことで直接数えることもできます。

実際には 0 を 1 に置き換える操作を考慮する必要があります。つまり 0 が $A$ 個以上連続している領域は、 $j$ が表現している「直前の連続している 1 の個数」に加えてあげる必要がある、ということです。

これを処理するために添字を増やします。 $dp\lbrack i \rbrack\lbrack j \rbrack\lbrack l \rbrack\lbrack f \rbrack$ を以下のように定義します。

前から $i$ 文字を決めて、
直前の連続している「1 または $A$ 個以上の連続した 0」の合計個数が $j$ 個であって、
直前の文字が $l$ であって、
直前が連続した $A$ 個以上の 0 である（ $f=1$ ）/ない（ $f=0$ ）状態で、
これまでの遷移で $j \ge B$ となったことがないような01文字列の個数

$dp\lbrack i \rbrack\lbrack j \rbrack\lbrack l \rbrack\lbrack f \rbrack$ からの遷移を考えましょう。まず普通に 1 または 0 を足す遷移では遷移後の状態は以下のようになります。

1 を足した場合、 $j$ は $1$ 増え、 $l$ は $1$ になり、 $f$ は $0$ になる。
0 を足した場合、もし遷移前の $f$ が $1$ であれば $j$ が $1$ 増えて遷移する。そうでなければ、 $j, l$ がともに $0$ になって遷移する。

それとは別に、 $i \le N-A$ のときは「0 が $A$ 個連続する領域が始まる」という遷移を特別に考える必要があります。これは最初または 1 の直後のみ行います（このためにフラグ $l$ があります）。この時の遷移は、

$dp\lbrack i+A \rbrack\lbrack j+A \rbrack\lbrack 0 \rbrack\lbrack 1 \rbrack$ に係数 $1$ で遷移する。
その代わり「普通に 0 を $A$ 回連打した遷移」を算入してはいけないので、そのときの遷移先である $dp\lbrack i+A \rbrack\lbrack 0 \rbrack\lbrack 0 \rbrack\lbrack 0 \rbrack$ にあらかじめ係数 $-1$ で遷移しておくことで打ち消す。