はまったのが解説にない部分だったので、
同じはまり方をした人には役立つかも。
問題文：AGC046D
できあがる文字列をTとする。
Tの各文字は、以下のいずれか：
- ★ 元から文字列Sの「右側」にあり、操作を受けなかったもの
- △ 元は、文字列Sの「左側」にあり、操作を受けて挿入されたもの
★と△の決め方は複数あるが、
数え上げるために、★の位置を以下の方法で貪欲に1つに決める。
「文字列Sの右端から順に、Tのできるだけ右にくるように対応づける」
その上で、対応付いた分をあらためて「右側」とする。
すると△は、
左にある一番近い★と反対の数字（0なら1、1なら0）・・・（※）
になる。
そこで、「右側」を全通り試し、数え上げる。
具体的には、S[0]～S[i]を「左側」、残りを「右側」とし、
iを全通り試す。
- 「左側」から0を
j個、1をk個供給することが可能か否かdpA[i][j][k] - 「右側」に、0を
j個、1をk個挿入してできる文字列の個数dpB[i][j][k]
を計算し、可能な組合せを全部足したものが答。
dpB[i][j][k]の計算
iの大きい方から順に以下の通り計算することができる。
今、i=iの時の計算をしようとしているとする。
S[i]=0の時
（※）で書いた通り、S[i]の右に1を挿入する。
i=i+1の時点で1がk個以下なら、
i=iで1をk個にできるので、それらの和を取ればよい。
dpB[i][j][k]=Σ_{k'=0}^k dpB[i+1][j][k']
これはimos法の時と同じ操作で求まるので、
計算量は$O(N^3)$（$N$はSの長さ）。
S[i]=1の時
S[i]の右に0を挿入する。S[i]=0の時と同様に考えると、以下の通りになる。
dpB[i][j][k]=Σ_{j'=0}^j dpB[i+1][j'][k]
dpA[i][j][k]の計算
配るDPで考える。
dpA[i][j][k]が「可能」なら、
次の2つ(S[i+1]とS[i+2])のどちらかを供給に回すことができるので、
dpA[i+2][j+1][k ] ←「可能」（次の2つのどちらかに0がある時）
dpA[i+2][j ][k+1] ←「可能」（次の2つのどちらかに1がある時）
とできる。
また、次の2つのうち右側(S[i+2])をその場に「挿入」することで、
何もせずにiを1つ進めることができる。
dpA[i+1][j][k] ←「可能」
これをしないと、
0011000000…のようになっている時に、1を2つ供給できない。
区切りを1つずらすことで2つとも供給に回せる。
更にもう1つ遷移を考える必要がある。これに気づかず大はまりした。
もう1つの遷移を考えずにはまった様子
その結果、S=111001の時に、
正解が25個なのに24個と答えているのを見つけた。
正解25個の文字列をダンプすると、「100」がある。
・・・
どう見ても100が作れるように見えない。
100を作るためには、2つの0を供給する側に回す必要があるが、
2つとも供給するのは不可能に見える。
・・・
1分くらい考えて、ようやく気が付いた。
先に0と0の間に1を挿入して2つの0を分離しておけば、2つとも供給できる！
もう1つの遷移として、次の1つ(S[i+1])を供給に回す操作が可能。
次の1つが0なら、供給に回す予定だった1を一つ取り崩し、
0の後ろに挿入すれば、0を供給に回せる。
次の1つ(S[i+1])が1なら、その反対の操作をする。
dpA[i+1][j+1][k-1] ←「可能」(次が0の時)
dpA[i+1][j-1][k+1] ←「可能」(次が1の時)
結局、dpA[i][j][k]の遷移を全部まとめると、以下となる。
dpA[i][j][k]が「可能」の時のみ以下の遷移を実施：
dpA[i+2][j+1][k ] ←「可能」(S[i+1]とS[i+2]のどちらかに0がある時)
dpA[i+2][j ][k+1] ←「可能」(S[i+1]とS[i+2]のどちらかに1がある時)
dpA[i+1][j ][k ] ←「可能」
dpA[i+1][j+1][k-1] ←「可能」(S[i+1]が0の時)
dpA[i+1][j-1][k+1] ←「可能」(S[i+1]が1の時)
計算量はこちらも$O(N^3)$なので、全体も$O(N^3)$で解ける。
本番では、問題だけ読んだがやらずに避けた。
後から解いてみると、案の定どっぷりはまったので、避けて正解だった。