記法について

A および B からなる文字列 \(U = U_1 U_2 \dots U_{|U|}\) に対し，長さ \(|U|\) の数列 \(A(U)\) を，

• \(A(U)_1 = \begin{cases} 1 & (U_i = `A`)\\ -1 & (U_i = `B`) \end{cases}\),
  
• \(A(U)_{i} = A(U)_{i-1} + \begin{cases} 1 & (U_i = `A`)\\ -1 & (U_i = `B`) \end{cases} \quad (2 \le i \le |S|)\)

により定める．\(A(U)\) は \(U\) の文字 A, B をそれぞれ \(\pm 1 \) に置き換えて累積和を取ったものである．

一致させることが可能になる条件

以下では一般性を失わず \(X \ge Y\) とする．まず \(S\) と \(T\) を一致させられるかどうかについて考える． 結論から述べると，以下の条件を全て満たす写像 \(f \colon \{ 1, \dots, |S|\} \to \{ 1, \dots, |T| \}\) が存在することが，\(S\) と \(T\) を一致させることが可能なことと同値である：

• \(f(1) < f(2) < \dots < f(|S|)\),
• \(S_i = T_{f(i)} \ (1 \le i \le |S|)\),
• \(A(S)_i = A(T)_{f(i)} \ (1 \le i \le |S|)\)

この条件について簡単に説明する．\(f(i)\) は挿入の前後で \(S_i\) が \(T\) の何文字目に移動するかに対応している．1 番目の条件は各文字の相対順序が挿入の前後で変化しないことに対応している．また 2 番目の条件は挿入の前後で各文字が変化しないことに対応している．また挿入は AB あるいは BA という形でしか行えないため，挿入の前後で，(挿入された部分以外の) 累積和が変化しない．これが 3 番目の条件に対応している．

コストの最小化

\(S\) と \(T\) を一致させることが可能な場合，操作回数は \((|T| - |S|) / 2\) である．よって AB の挿入回数を最小化すればよい．

写像 \(f \colon \{ 1, \dots, |S|\} \to \{ 1, \dots, |T| \}\) が上記の条件を満たしているとして，挿入の前後で，\(S\) の \(i\) 番目の文字 (\(S_i\) とする) が \(T\) の \(f(i)\) 番目の文字に対応するように挿入を行うことを考える．このとき \(S_i\) と \(S_{i+1}\) の間に AB を挿入する回数の最小値は

\[ \max_{f(i) \le j < f(i+1)} A(T)_j - A(T)_{f(i)} = \max_{f(i) \le j < f(i+1)} A(T)_j - A(S)_{i} \quad (*) \]

に等しいことが分かる．このことは，BA の挿入によっては累積和の最大値が増加しないこと，および実際にこの回数の AB の挿入と，何回かの BA の挿入により \(T_{f(i)+1}T_{f(i)+2}\dots T_{f(i+1)-1}\) の部分を生成できることにより示すことができる．\(S\) の先頭と末尾に必要な AB の挿入回数も同様に計算できる．

アルゴリズム

上記を利用すると，\(\mathrm{DP}[i][j] \coloneqq (f(i) = j \text{ のときのコストの最小値})\) として，この DP テーブルを \((i, j)\) の昇順に求める \(O(|T|^3)\) の DP ができるが，これでは制限時間に間に合わない．

\((*)\) 式の形を利用すると，スタックを用いてこれを \(O(|T|^2)\) に高速化できる．具体的には，各 \(1 \le i \le |S|\) に対して以下を行う： \((コストの最小値, 累積和の最大値)\) というペアを詰めたスタックを用意して \(\mathrm{DP}[i][*]\) を更新していく．詳しくは実装例を参照されたい．