AGC049 B - Flip Digits - ツバサの備忘録

解法

できる操作が、

1 をひとつ左に動かす
連続する1 を消す

のどちらかとなっています。
また、右側にある 1 が、一つ左側の 1 を追い越すことはできません(そもそも、追い越したいのであれば、左側の 1 を動かせばよいです)。そのため、元々 $S$ で与えられた 1 の順序は変化しないまま、左に移動するか、消えるか、その位置のままか、のパターンしかありえないことがわかります。
$S_{i}$ が 1 のときに左に移動させる(もしくは据え置き)パターンは、それより左側に、まだ位置を確定させていない 1が存在しないが、 $T_{j} (j \leq i)$ が 1 となっているものが存在するパターンです。 $j$ が最小となっている箇所に優先的に移動させないといけないため、 $i-j$ 回の操作が必要になります。
$S_{i}$ が 1 のときに消すパターンは、上記のような $j$ が存在しないときです。どこへ移動させても $T$ と一致することがないので、 $S_{k}(i \lt k)$ が 1 となっている最小の $k$ を見つけ、その 1 と合わせて打ち消します。これにはコストが $k-i$ かかります。
以上のことをシミュレートし、最終的に $S$ と $T$ が一致すればよいです。
queueを2つ使い、 $S$ と $T$ でまだ消すべきなのに消してない/ 1にすべきなのに $S_{i}$ が1になっていない位置をメモし、消すべき1から優先的に上記の処理を行います。