まずは，ある文字列 \(s\) が空文字列へと変換可能である条件を考えてみましょう．

実験，あるいは直感によって，空文字列へ変換可能な文字列について，次のような条件を見出すことができます．

• 長さが偶数である．
• 以下のような形でない （記法の意味は正規表現に従います）
  • \(s=\)A[AA|BA|BB]*B

これが実際に必要十分であることは，帰納法で証明することができます（詳細は省略します）． 以降，空文字列に変換可能な文字列を，削除可能な文字列，と呼ぶことにします．

次に，ある文字列 \( s,t\) について，\(s\) を \(t\) に変換可能であるかを判定することを考えます．

一番最初に思いつくのは貪欲法です． つまり，以下のような判定方法が考えられます．

• \(x=0\) とする．
• \(i=1,2,\cdots,|t|\) について以下の操作を行う．
  • \(s[x+1,y-1]\) が削除可能かつ，\(s_y=t_i\) を満たす最小の \(y\) (\(x<y\)) を選び，\(x\) を \(y\) で置き換える．そのような \(y\) が存在しない場合は変換不可能と報告．
• \(s[x+1,|s|]\) が削除可能なら変換可能，そうでないなら不可能．

このアルゴリズムは正しくありません． 例えば，\(S=\)BABB, \(t=\)BB で間違えます． これは，\(t_i=\)B の場合には，最小の \(y\) を取るのが最適とは限らないためです．

ここで，次の性質に注目します．

• \(s[x+1,y-1]\) が削除可能かつ \(s_y=\)B ならば，\(y<z\), \(y \equiv z \mod 2\), \(s_z\)=B を満たす任意の \(z\) について，\(s[x+1,z-1]\) が削除可能．

これを元に，上記の貪欲法を修正した次のような判定方法を考えることができます．

• \(x=0\) とする．
• \(i=1,2,\cdots,|t|\) について以下の操作を行う．
  • \(x=0\) もしくは \(s_x=\)A の場合： \(s[x+1,y-1]\) が削除可能かつ，\(s_y=t_i\) を満たす最小の \(y\) (\(x<y\)) を選び，\(x\) を \(y\) で置き換える．そのような \(y\) が存在しない場合は変換不可能と報告．
  • \(s_x=\)B の場合：\(x \leq x'\), \(x \equiv x' \mod 2\), \(s_{x'}\)=B を満たすすべての \(x'\) を考える．\(s[x'+1,y-1]\) が削除可能かつ，\(s_y=t_i\) を満たす最小の \(y\) (\(x'<y\)) を選び，\(x\) を \(y\) で置き換える．そのような \(y\) が存在しない場合は変換不可能と報告．
• \(s[x+1,|s|]\) が削除可能なら変換可能．また，\(s_x=\)B の場合は，\(x \leq x'\), \(x \equiv x' \mod 2\), \(s_{x'}\)=B を満たすすべての \(x'\) を考え，\(s[x'+1,|s|]\) が削除可能な \(x'\) があれば変換可能．それ以外の場合は不可能と報告．

実はこの判定アルゴリズムは正しいことが証明できます． まず，上の判定アルゴリズムをきちんと整理すると，以下のような操作になります．

• \(x=0\) とする．
• \(i=1,2,\cdots,|t|\) について以下の操作を行う．
  • \(x=0\) もしくは \(s_x=\)A の場合：
    • \(t_i=\)A の場合：\(x<y\), \(x \not \equiv y \mod 2\), \(s_y=\)A を満たす最小の \(y\) をとり，\(x\) を \(y\) で置き換える．
    • \(t_i=\)B の場合：\(x<y\), \(x \not \equiv y \mod 2\), \((s_{y-1},s_y)=(\)A,B\()\) を満たす最小の \(y\) をとり，\(x\) を \(y\) で置き換える．（便宜上，\(s_0=\)A とする）
  • \(s_x=\)B の場合：\(x<y\), \(x \not \equiv y \mod 2\), \(s_y=t_i\) を満たす最小の \(y\) をとり，\(x\) を \(y\) で置き換える．
  • そのような \(y\) が存在しない場合は変換不可能と報告．
• \(s[x+1,|s|]\) が削除可能なら変換可能．また，\(s_x=\)B の場合は，\(x \leq x'\), \(x \equiv x' \mod 2\), \(s_{x'}\)=B を満たすすべての \(x'\) を考え，\(s[x'+1,|s|]\) が削除可能な \(x'\) があれば変換可能．それ以外の場合は不可能と報告．

正当性の証明の方針としては，各 \(i\) について，\(t[1,i]\) を \(s\) から取り出す際，\(t_i\) が対応する位置として考えられる最小のものが \(x\) であることを示します． 上のように判定アルゴリズムを整理してあれば，背理法によってこれを確認するのは容易です．

あとはこの判定アルゴリズムをそのまま数え上げの DP に直せば，元の問題を解くことができます． 計算量は \(O(N)\) です．

解答例(C++)