ABC310E

DP解

この記事はkyopro_friendsさんの解説を自分なりに理解した際のメモ。
解放ありきで考えてるので、なぜこういう考えが浮かんでくるのかは説明していない。

DP配列dp[j][k]を考える
f(i, j) = k(0 or 1) になるiの個数(1<=i<=j)とする。

具体的に$f(i, j)$がどのような値になるか書き出してみる。
入力例 1
$N=5, S=00110$

\begin{align}
f(1, 1) &= A_{1} = 0\\
\\
f(2, 2) &= A_{2} = 0\\
f(1, 2) &= f(1, 1) ⊼ A_{2}\\
        &= A_{1} ⊼ A_{2}\\
\\
f(3, 3) &= A_{3} = 1\\
f(2, 3) &= f(2, 2) ⊼ A_{3}\\
        &= A_{2} ⊼ A_{3}\\
f(1, 3) &= f(1, 2) ⊼ A_{3}\\
        &= A_{1} ⊼ A_{2} ⊼ A_{3}\\
\\
f(4, 4) &= A_{4} = 1\\
f(3, 4) &= f(3, 3) ⊼ A_{4}\\
        &= A_{3} ⊼ A_{4}\\
f(2, 4) &= f(2, 3) ⊼ A_{4}\\
        &= A_{2} ⊼ A_{3} ⊼ A_{4}\\
f(1, 4) &= f(1, 3) ⊼ A_{4}\\
        &= A_{1} ⊼ A_{2} ⊼ A_{3} ⊼ A_{4}\\
\\
f(5, 5) &= A_{5} = 0\\
f(4, 5) &= f(4, 4) ⊼ A_{5}\\
        &= A_{4} ⊼ A_{5}\\
f(3, 5) &= f(3, 4) ⊼ A_{5}\\
        &= A_{3} ⊼ A_{4} ⊼ A_{5}\\
f(2, 5) &= f(2, 4) ⊼ A_{5}\\
        &= A_{2} ⊼ A_{3} ⊼ A_{4} ⊼ A_{5}\\
f(1, 5) &= f(1, 4) ⊼ A_{5}\\
        &= A_{1} ⊼ A_{2} ⊼ A_{3} ⊼ A_{4} ⊼ A_{5}\\
\end{align}

ここで、$f(4, 4)$〜$f(1, 4)$を抜き出してみる。

\begin{align}
f(4, 4) &= A_{4} = 1\\
f(3, 4) &= f(3, 3) ⊼ A_{4}\\
        &= A_{3} ⊼ A_{4}\\
f(2, 4) &= f(2, 3) ⊼ A_{4}\\
        &= A_{2} ⊼ A_{3} ⊼ A_{4}\\
f(1, 4) &= f(1, 3) ⊼ A_{4}\\
        &= A_{1} ⊼ A_{2} ⊼ A_{3} ⊼ A_{4}\\
\end{align}

$f(4, 4)$〜$f(1, 4)$はDP配列ではDP[4][k]に該当する。
$f(4, 4)$以外の右辺の最初の項に注目してみると、$f(3, 3)$〜$f(1, 3)$となっている。
これはDP[3][k]に該当する。
$f(3, 3)$〜$f(1, 3)$は1か0しか取らないので、
右辺のそれぞれの値は$0⊼A_{4}$と$1⊼A_{4}$の2通りしかない。
そうすると$f(3, 3)$〜$f(1, 3)$に含まれる0と1の個数が欲しい気持ちになってくる。
具体的に$f(3, 3)$や$f(2, 3)$の値がわからなくても、
$f(3, 3)$〜$f(1, 3)$の中の0と1の個数が分かれば$f(3, 4)$〜$f(1, 4)$の中の0と1の個数がわかるのだ。

DPの遷移としては以下のようになる。

dp[j][nand(Ai, 0)] += dp[j-1][0];
dp[j][nand(Ai, 1)] += dp[j-1][1];

上記の説明だとこれが漏れているのでこれも足そう。

f(4, 4) = A_{4} = 1

dp[j][Ai] += 1;

さて、ここまでの説明で以下の値を得ることができた。

dp[1][0]
dp[1][1]
dp[2][0]
dp[2][1]
dp[3][0]
dp[3][1]
dp[4][0] // f(1, 1)~f(4, 4) のうち0となる数
dp[4][1] // f(1, 1)~f(4, 4) のうち1となる数
dp[5][0]
dp[5][1]

最終的に求めたい値は、以下なのであるがこのうち0は足しても意味がないので1だけ考える。

f(1, 1)
+ f(2, 2)〜f(1, 2)
+ f(3, 3)〜f(1, 3)
+ f(4, 4)〜f(1, 4)
+ f(5, 5)〜f(1, 5)

つまり求めたい値は以下となる。

dp[1][1] + dp[2][1] + dp[3][1] + dp[4][1] + dp[5][1]

以上です。