はまったのが解説にない部分だったので、
同じはまり方をした人には役立つかも。

問題文：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つの遷移を考えずにはまった様子

以上を実装すると、入力例3が合わない。しかし文字列Sが長すぎて原因が分からない。挫折しかけたが、もう少し頑張ってみた。問題文の操作を愚直に実行して数えあげるコードを作成。文字列Sが短ければこれで正解が分かるので、正解と食い違うできるだけ短い文字列Sを色々手入力して探す。

その結果、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)$で解ける。

本番では、問題だけ読んだがやらずに避けた。
後から解いてみると、案の定どっぷりはまったので、避けて正解だった。