本問題は下記の通りに言い換えられます。

次の操作を好きな回数行って、\(A\) を \(B\) に作り替えることができるか？可能なら操作回数の最小値を求めよ。

• \(A\) の前後に 0 を \(1\) 個ずつ追加し、その後連続するいずれかの \(3\) 文字をその最大値（すなわち、その \(3\) 文字の中に 1 が含まれていれば 1 、そうでなければ 0 ）で置き換える。

これを解くために、まず「ちょうど \(x\) 回の操作で \(A\) を \(B\) に作り替えることが可能か？」という判定問題の答え \(P(x)\) を考えます。 これは、

\(A\) の前後に 0 を \(x\) 個ずつ追加した文字列 \(A^{(x)} \coloneqq \)0\(^x A\)0\(^x\) を、\(N\) 個の奇数長の連続部分文字列に分割し、各部分文字列をその最大値に置き換えることで \(B\) を作れるか？

という問題となります。 \(P(x) = \mathrm{true}\) となるには、少なくとも、\(A^{(x)}\) の先頭・末尾それぞれに続く 0 の個数が、\(B\) の先頭・末尾のそれと同数以上でなければなりません。 すなわち、文字列 \(s\) に対して、\(s\) の先頭・末尾に続く 0 の個数をそれぞれ \(L(s), R(s)\) で表すとき、

\[L(A) +x = L(A^{(x)}) \geq L(B), \quad R(A) + x = R(A^{(x)}) \geq R(B)\]

が必要です。このことから \(P(x) = \mathrm{true}\) の必要条件

\[x \geq m \coloneqq \max\{L(T)-L(S), R(T)-R(S)\} \tag{1}\]

が得られます。以下、(1) を仮定します。

\(P(x)\) を求めることは、\(B\) を先頭から順に作るために、対応する \(A^{(x)}\) 側の部分文字列を貪欲に決定して切り出ていくアルゴリズムによって判定できます。 具体的には、\(A' \gets A^{(x)}\) と初期化、\(B\) の 0 が連長圧縮されているとし、下記の手順にしたがって \(B\) を先頭から作っていきます。

• \(B\) 側の1を作りたいとき： \(A'\) の prefix で 1 を含む最短のものを切り出す。 ただし \(B\) の最後の 1 を作るときは、\(A'\) のすべての 1 を使い切る必要があるため、最後の 1 を含む最短の奇数長の prefix を切り出す。

• \(B\) 側の 0\(^k\) を作りたいとき： \(A'\) の先頭から 0 を \(k\) 回切り出せば良いが、そのためには \(A'\) が 0\(^k\) を prefix に持つ必要がある。 もしそれが満たされていない場合、\(A'\) の先頭に 0\(^k\) が現れるまでまで 「直前の \(B\) 側の 1 を作るために切り出した部分文字列の長さがもう \(2\) 文字分長かったことにして \(A'\) の先頭を \(2\) 文字削除する」という修正を繰り返す（式 (1) を仮定しているためこの修正が必要となる際には「直前の \(B\) 側の 1 を作る操作 」をたしかに行なっています）。

以上によって、与えられた \(x\) に対する \(P(x)\) を \(O(N)\) 時間で求められます（途中で \(A'\) から部分列を切り出せなくなった場合、\(P(x) = \mathrm{false}\) と判定できます）

一方、

\[(x \geq m+2 \,\,\text{かつ}\,\, P(x) = \mathrm{true}) \implies P(x-2) = \mathrm{true} \tag{2}\]

が成り立ちます。 なぜなら、\(x \geq m+2, P(x) = \mathrm{true} \) のとき上記の貪欲アルゴリズムは \(A^{(x)}\) をある \(k, k', l \geq 0\) と文字列 \(s_1, \ldots, s_l\) によって

\[A^{(x)} = \underbrace{0|0|\ldots|0}_{L(B)}|0^{k+2}s_1|s_2|s_3|\ldots|s_l|\underbrace{0|0|\ldots|0}_{R(B)-1}|0^{k'+3}\]

で表される形で \(N\) 個の部分文字列に分解しますが、これをもとに \(A^{(x-2)}\) の分解

\[A^{(x-2)} = \underbrace{0|0|\ldots|0}_{L(B)}|0^{k}s_1|s_2|s_3|\ldots|s_l|\underbrace{0|0|\ldots|0}_{R(B)-1}|0^{k'+1}\]

が得られるからです。

(1) と (2) から、本問題を解くには \(P(m)\) と \(P(m+1)\) だけを求めれば十分であり、本問題を全体で \(O(N)\) 時間で解くことができます。