AGC049 B

これが緑なんてたいがいにせえよ

問題
atcoder.jp

公式解説
atcoder.jp

マイ提出 (C++)
atcoder.jp

SとTの累積xorを取ると見やすくはなるがあんま本質ではなさそう。見やすいので以下累積xorで考えます。

まず最初のS, T不一致点 i まで移動します。それより左は問題に関与しません。
S 0000001
T 1101001

不一致点 i を一致させるにはSのS[i]と異なる文字が存在する最小の j > i から移動させるのが最小手筋です。そのようなjが存在しないとき解なし。操作回数はj-i。操作後はこう
S 1111111
T 1101001

i ~ jはすべて同じ文字となったので、次の不一致点 i' に対応する j' は j' > j となります。したがって、尺取法的に次のi', j'を探していけば O(N) で計算可能です。

答えは O(N^2) になるので int では不足します (1WA)。