文字列 \(S\) の 0 の位置に注目して考えます。

まず、操作 \(2\) (110 ⇆ 011) のみで作られる \(S\) の条件を考えます。
操作 \(2\) は 0 が \(2\) つ移動していると考えることができます。
この操作で各 0 の順序は入れ替わらないため、任意の \(i\) について、\(i\) 番目の 0 のindexの偶奇が変わらないことが必要条件です。
また、これは十分条件でもあります。
操作は可逆なので \(T\) に対して操作をしてもよく、\(S\) と \(T\) に対して 0 をできるだけ前になるように操作をすれば同じ文字列になるからです。

次に操作 \(1\) (001 ⇆ 100) の性質について考えます。
操作 \(1\) は \(2\) つの 0 のindexの偶奇を入れ替えていると考えることができます。
また、先ほどの議論より、各 0 のindexの偶奇が一致していれば、操作 \(2\) により文字列を一致させることができます。
よって、\(S,T\) の \(i\) 番目の 0 のindexを \(2\) で割ったあまりをそれぞれ \(x_i,y_i\) とすると、答えの下界は以下の通りです。

• \(x_i, x_{i+1}\) を入れ替えるという操作を行って \(y\) に一致させるために必要な操作回数の最小値。

そして、実際にこれが達成できます。

0,1 からなる数列の転倒数を求めれば良いので、この問題は \(O(N)\) で解くことができます。

下界が達成できることの証明

操作は可逆なので \(T\) に対しても操作をして良いものとします。

転倒数が \(1\) 以上のときに、必ずコスト \(1\) で転倒数を \(1\) 減らせることを示します。

一般性を失わず、以下を仮定します。

• \(S,T\) において、 0 の間に \(2\) つ以上の 1 が連続しない。
• \(x,y\) において、既に「正しい位置にある」要素は存在しない。 ( 存在していた場合、そこで列を分割して帰納法を行う。 )
  • \(x\) の \(k\) 番目の \(0\) と、\(y\) の \(k\) 番目の \(0\) が \(x,y\) の中で同じ index にあるとき、これらの要素は移動させる必要が無いため、「正しい位置にある」と言うことにします。 \(1\) についても同様とします。

\(x,y\) に同じ数字が隣接する箇所が存在しない場合

一般性を失わず、 \(x=(0,1,0,1,\cdots), y=(1,0,1,0,\cdots)\) として良いです。
このとき、 \(T=\)100… となっているため， \(T\) の最初の \(3\) 項に操作 \(1\) を行うことで転倒数を \(1\) 減らすことができます。

\(x,y\) の少なくとも一方に同じ数字が隣接する箇所が存在する場合

一般性を失わず、 \(x\) で \(0\) が隣接している箇所があるとして良いです。
\(x\) の中で \(0\) が隣接している極大な区間 \([l,r)\) を考えると、以下の少なくとも一方が成り立ちます。

• \(x\) の \(l\) 番目より前に含まれる \(1\) の個数 \(>\) \(y\) の \(l\) 番目より前に含まれる \(1\) の個数
• \(x\) の \(r\) 番目以降に含まれる \(1\) の個数 \(>\) \(y\) の \(r\) 番目以降含まれる \(1\) の個数

なぜなら、もし上記がいずれも成り立たないとすると、 \(x,y\) に含まれる \(0,1\) の個数は同じであるため、 \(y_l, y_{l+1}, \dots, y_{r-1}\) は全て \(0\) になりますが、\(y\) の \(l\) 番目より前に含まれる \(1\) の個数が \(x\) の\(l\) 番目より前に含まれる \(1\) の個数 と一致し、\(x_l\) と \(y_l\) が正しい位置にある要素となるため、 「\(x,y\) において正しい位置にある要素が存在しない」という仮定に矛盾するからです。

\(1\) つ目が成り立つ場合、\(l>0\) が成り立ち、 \(x_{l-1},x_l,x_{l+1} = 1,0,0\) となるため、その部分に対応する \(S\) は 0010 となります。これの 001 の部分の \(3\) 項に操作 \(1\) を行うことで転倒数を \(1\) 減らすことができます。
\(2\) つ目が成り立つ場合も同様です。