AGC045-C Range Set - kaage精進録

問題概要

長さ $N$ の文字列に対して、 $A$ 文字選んで 0 にする、 $B$ 文字選んで 1 にするという操作を好きなだけ行って生成できる文字列の個数を求めよ。

考察

10秒くらい考えると、 $A$ 文字選ぶ、というのは $A$ 文字以上選ぶ、というふうに言い換えられる。 $B$ でも同様である。また、 $A>B$ としても一般性を失わない。

ここで、「もしかして必要十分条件は $A$ 文字連続した 0, または $B$ 文字連続した 1 があることではないか？」と思うので、プログラムを書いて調べてみる。テストケース 2 で少し答えより多いので、目視して調べると「 $B$ 文字未満の 1 の連続している場所と両端について、どこか間に $A$ 文字以上の間隔がある場所が存在する」という条件が加わる。

これをDPして調べたいが、結局コンテスト中にはできなかった。

「 $B$ 文字以上連続する 1 をすべて 0 に置き換えたとき、 $A$ 文字以上 0 が連続している場所がある」と言い換えると多少見通しがよくなる。（文字列を頭の中でイメージすればそんなに変わらないが）

まず、 $dp\left[i\right]\left[j\right]$ を、 $i$ 文字目までで 0 が連続している長さが $j$ の通り数、と定義してみる。重複を避けるために、 $j\geq A$ となったら即座に答えに加えて遷移しない、また、1 の $B$ 連続についてはまとめて加える、という方針でやるが、これではうまくいかない。