[1] \(Y=A\) になる必要十分条件

最終的に \(Y=A\) になるための操作方法の必要条件を考えます。まず以下の条件が明らかです。

- 操作をする直前に、\(A\) の元が \(X\) に含まれている

- 操作をする直前に、\(X\) の最小値が \(A\) の元である必要もあります。 これをふまえると、さらに以下の条件が考えられます。

\(A_i\) が \(Y\) に入っていない状態で、+ 操作によって \(X\) に追加される値 \(x\) は、「\(x\) は \(A\) の元である」と「\(x > A_i\)」のいずれかを満たす

必要性を確認しましょう。\(A_i\) が \(Y\) に入っていない状態で、+ 操作によって、\(A\) の元ではない \(A_i\) 未満の値 \(x\) が追加されたと仮定します。すると、その後の操作で \(A_i\) が \(Y\) に追加される前に \(x\) が \(Y\) に追加されることになるので、最終的に \(Y=A\) になることはあり得ません。従って、必要性がわかりました。

\(2\) つの必要条件を合わせると、実は十分条件にもなっていることを確認しましょう。\(1\) つ目の条件より、- 操作の直前に\(A\) の元 \(A_i\) が \(X\) に含まれています。\(2\) つ目の条件より、\(X\) の元であって \(A\) の元でないものは全て \(A_i\) より大きいです。このことから、- 操作で \(Y\) に追加されるのは必ず \(A\) の元となることが言えるので、最終的に \(Y=A\) となります。よって、十分性が示されました。

以上をまとめると、\(Y=A\) になる必要十分条件は以下の通りです。

• - 操作をする直前に、\(A\) の元が \(X\) に含まれている
• + 操作をする直前の \(Y\) に含まれていない \(A\) の元の最大値を \(A_j\) (全て \(Y\) に含まれているなら \(0\)) とすると、\(X\) に追加する値は「\(A\) の元」、「\(A\) に含まれない \(A_j\) より大きい値」のいずれかである

---

[2] 動的計画法

前準備として、\(A\) を降順ソートして \(A_0 > A_1 > \cdots > A_{M-1}\) となるようにします。また、便宜的に \(A_M = 0\) とします。

前述の必要十分条件を元に動的計画法を構成していきますが、主なアイデアは以下の通りです。

• + 操作で値を \(X\) に入れるとき、\(A\) に含まれない値ならばその場で値を決め、\(A\) に含まれる値ならば具体的な値の決定を後回しにする。
• - 操作では、\(X\) に入っている \(A\) の元を \(Y\) に入れる。このとき、\(Y\) に追加する \(A\) の元が、\(Y\) に含まれない \(A\) の元の最大値であるかどうかによって場合分けする。

具体的な dp の設計は以下の通りです。

\(\mathrm{dp}(i,j,k,f)\coloneqq\) 「\(S\) の先頭 \(i\) 文字の操作を処理した後、\(Y\) に入っていない最大の \(A\) の要素が \(A_j\)、\(X\) に入っている \(A\) の要素（値は未確定）は \( k\) 個、\(X\) に \(A_j\) が入っているかの bool 値が \(f\)」となるような、\(i\) 回目までの \(X\) への追加の仕方の場合の数

dp の初期化は \(\mathrm{dp}(0,0,0,0) = 1\) で、最終的に求める答えは \(\mathrm{dp}(N+M,M,0,0)\) となります。

dp の各段において、\(Y\) に入っている値が確定済みの元は \(A_0,...,A_{j-1}\) だけとなるようにします。すると、\(Y\) に入っている \(A\) の要素で値が未確定のものの個数 \(\ell\) は、\(\ell = (S[0:i]\) の - の個数\()- j\) となるので、\((i,j,k)\) によって一意に定まります。

dp の遷移については、以下のように記述できます。

• + 操作で \(A\) に含まれない値を入れる場合は、まだ \(X,Y\) に入っていない \(A_j\) より大きい \(A\) に含まれない値の個数を数えることで、\(N - A_j - j - (i - (S[0:i]\) の - の個数\()\times2 - k)\) 通りある。\(A\) に含まれる値を入れる場合は \(k\) をインクリメントし、\(f = 0\) の場合は入れる値を \(A_j\) にするかどうかを決める。

• - 操作では、\(X\) に入っている \(A\) の要素を \(Y\) に入れるので \(k\) をデクリメントする。\(k=1\) かつ \(f=1\) の場合に限って \(Y\) に追加される値が \(A_j\) となるため、\(j\) をインクリメントする。さらに、\(k=1\) かつ \(f=1\) のとき、\(Y\) に入っている \(A\) の元で値が未確定のもの \(\ell\) 個のうち \(m\) 個を \(A_{j+1},A_{j+2},\dots,A_{j+m}\) に割り当てると、次の遷移先の \(j\) の値は \(j+m+1\) になる。

\(k=f=1\) の状態で - 操作をすると、\(X\) には \(A\) の元は含まれなくなります。\(Y\) に入っている値が未確定の要素は全て \(A_j\) 未満の \(A\) の元であるため、それらにどのように (\(X\) に挿入するときに、\(A_j\) 未満の \(A\) の元の) 値を割り当てていたことにしても、この - 操作後には「\(X\) に \(A\) の元は含まれていない」という状態になるのがポイントです。これによって、\(Y\) に入っている値が未確定の要素に対して、\(A_j\) 未満の\(A\) の元を自由に割り当てることが可能となります。

dp の状態数は \((N+M+1)\times (M+1)\times (M+1)\times 2\)、遷移先は \(k=f=1\) のとき \(O(M)\) 個、それ以外のとき \(O(1)\) 個なので、全体の計算量は \(O((N+M)M^2)\) です。