AGC045-C Range Set

問題: atcoder.jp

解説を読んで理解したつもりけど、どうやって $\mathcal{O}(N^{2})$ のDPを実装するかわからない人向けな解説

$0$ が $A$ 個以上連続せず、 $1$ が $B$ 個以上連続しないような長さ $N$ の列の個数

$dp_{i, 0}$ : $0$ で終わる長さ $i$ の列の個数
$dp_{i, 1}$ : $1$ で終わる長さ $i$ の列の個数

さらに $dp_{0, 0} = dp_{0, 1} = 1$ とおくと、

$dp_{i, 0} = \sum_{k = \max(0, i-A+1)}^{i-1} dp_{k, 1}$
$dp_{i, 1} = \sum_{k = \max(0, i-B+1)}^{i-1} dp_{k, 0}$

これは $i$ の小さい順に配るDPをすることで $\mathcal{O}(N(A+B))$ で求まります

(ここから蛇足パート)

ちなみに $0$ を何個かくっつける、その次に $1$ を何個かくっつける、・・・、というように見ると

$dpa_{i, j}$ : $i$ 回操作したときの長さ $j$ の列の個数 (先に $0$ を追加する場合)
$dpb_{i, j}$ : $i$ 回操作したときの長さ $j$ の列の個数 (先に $1$ を追加する場合)

を計算することでも求まります。愚直に書くと $\mathcal{O}(N^{2} \max(A, B))$ となり間に合いませんが、累積和を使って $\mathcal{O}(N^{2})$ に高速化できます。ただし、後になって係数をかけることを考えると残念ながら累積和による高速化でこの問題を解くことはできず、この実装はお蔵入りとなります。 (コンテスト中はここまで書いてサンプル2以降が合わずに終わりました・・・)

(ここまで蛇足パート)

$1$ が $n$ 個連続する部分に $0$ を $A$ 個以上連続させるように入れる方法が何通りあるかを数えておけば良い

これも上と同様にして、以下のように設定します:

$dpc_{i, 0}$ : $1$ で始まり $0$ で終わる長さ $i$ の列の個数
$dpc_{i, 1}$ : $1$ で始まり $1$ で終わる長さ $i$ の列の個数

$1$ で始まるようにしたいので、初期値は $dpc_{1, 0} = 0, dpc_{1, 1} = 1$ です。遷移は以下のようになり、これも $i$ の小さい順に配るDPをすれば求まります。

$dpc_{i, 0} = \sum_{k=1}^{i-A} dpc_{k, 1}$
$dpc_{i, 1} = dpc_{i-1, 0} + dpc_{i-1, 1}$

上記の DP の遷移で $n$ 個の $1$ を付け足すときに，今求めた値をかければ良いです

ここがこの問題の肝になるところだと思います (解説ACしようとしたとき私はここでかなり詰まりました)。 $n$ 個の $1$ を付け足すとき、はじめ or/and おわりは $0$ と隣接しています。そのため $0$ と混ざらないように、はじめ or/and おわりを $1$ にする必要があります。つまり、両端を $1$ にする必要がある場合は $dpc_{n, 1}$ を、少なくも片端を $1$ にする必要がある場合(つまり左端か右端になる場合)は $dpc_{n, 0} + dpc_{n, 1}$ をかければ良いです。最終的な遷移は以下のようになります。