AGC-Bにしては大分簡単な問題だった気もしますが，だからこそ瞬殺できるようにしたいです． 考察をまとめておきます．
問題概要
$ 0 $ と $ 1 $ からなる長さ $ N $ の文字列 $ S, T $ が与えられて $ S $ に対して以下のような操作を任意の回数行える．
- $ S_i = 1 (2 \leq i \leq N) $ を選択する．$ S_i $ を $ 0 $ に， $ S_{i-1} $ を $ 1 $ なら $ 0 $ に $ 0 $ なら $ 1 $ に置き換える．
この操作を任意回行って $ S $ と $ T $ を一致させることができるならその最小回数を答えよ．
制約
- $ 1 \leq N \leq 5 \times 10^{5} $
考察
まず操作の内容を考えてみる．
$ S_i = 1 $ のような $ i $ に対して操作を行うことができ， $ S_{i-1} = 0 $ のときは $ 1 $ を $ 1 $ つ左に移動する操作だと言い換えられる．一方， $ S _ {i-1} = 1 $ のときは隣接する $ 1 $ を $ 0 $ に変える操作だと言い換えられる．
したがって操作によって $ 1 $ を左に移動することと，隣接する $ 1 $ を $ 0 $ に変えることのみが可能だとわかる．
この考察から「 $ T $ にある $ T_i = 1 $ を $ S_j (i < j) = 1 $ を満たすなるべく近い $ j $ とマッチングしたい」と考えることは自然だと思う．ただし，この「マッチング」とは $ S $ 中の $ 1 $ を目標の位置までもっていくことを指して言っている．
ただし上のような例があるように，最も近いものとマッチングすると余ったもの同士が消せないことが起こり得る．これは左側に $ 1 $ が余った状態でマッチングをしてしまったためである．そもそも $ S $ と $ T $ が一致するためには $ T $ の一番左の $ 1 $ より左側にある $ S $ 中の $ 1 $ は必ず $ 0 $ にしておく必要がある．
$ 1 $ を $ 0 $ にする手段は隣接する $ 1 $ を両方 $ 0 $ にする以外に存在しないだめ， $ 2 $ 個ずつ $ 0 $ に変えていく必要がある． $ 0 $ にしなければならない $ 1 $ がなくなったらその時点で $ T $ と $ S $ の一番左の $ 1 $ と同士でマッチングすることができ，これが一番近い（下図）．
$ 1 $ を余分に偶数個 $ 0 $ に変えてからマッチングさせることも可能だが，可能な限り一番近くの $ 1 $ 同士をマッチングさせることが最適である．この証明は割愛するが遠くにマッチングすることで解が改善することはないことを示せばいいので，そう難しくはないだろう（自明と言えるほどでもない気がするが…）．
以上のような手続きを $ T $ の $ 1 $ が全てマッチング済みになるまで続けて矛盾が生じた場合に $ -1 $ を出力して終了すればよい．左端から $ 1 $ 個や $ 2 $ 個取り出す操作をしたいため $ 2 $ つの $ queue $ などを用いて実装すると楽かもしれない．
別解（？）
基本的な考え方は上の解法と同じ．ただ最適な解を求めるもう一つの方法が考えられる．実は最初に示したダメな最も近いマッチングの例のまま残った $ 1 $ 同士を $ 0 $ に変えていけば最適解と同じ操作回数が得られる．
場合分けによって簡単に説明する．
最も近いマッチングで左側に余る $ 1 $ の数が偶数個だった場合明らかに上で示した最適解と同じである．
最も近いマッチングで左側に余る $ 1 $ の数が奇数個だった場合，$ 1 $ を消す過程で右側にあった $ 1 $ が左側の $ 1 $ を必ず追い越す．この追い越しは操作上不可能だが手順を弄れば同じ操作回数で追い越しなしで必ず実現できる．
以上よりこちらの解法でも最適解が得られる．
個人的なポイント
- 式によって操作内容が書かれている場合はわかりやすく言い換えができないか考える
- 必ず満たすべき条件を見つけていくことによって状況を絞り込める
- 今回はどれともマッチングできない $ S $ 中の $ 1 $ 削除しなければならないことから最適解を導けた
- 貪欲はちゃんと正当性を確認する（今回実はたいして確認していなかったので反省）
- フリップの問題なので $ xor $ を考えるという筋も存在したようだ．今後のために発想としては持っておきたい
