\(X\) に対する \(4\) つの操作である、先頭への追加、先頭の削除、末尾への追加、末尾の削除をそれぞれ +L 、-L 、+R 、-R で表します。

・ \(X\) と \(Y\) が共通の整数を持つ場合

\(X\) と \(Y\) の両方の連続部分列であるような最長の数列を \(S\) とすると、最適な操作列は

• まず、-L と -R の繰り返しによって \(X\) を \(S\) に一致させ、
• その後、+L と +R の繰り返しによって \(X\) を \(Y\) に一致させる

ことであり、このときの操作回数は \(|X| + |Y| - 2|S|\) 回です。

\(S\) は接尾辞配列と LCP 配列を用いて \(\mathrm{O}(N)\) 時間で求められます。

・ \(X\) と \(Y\) が共通の整数を持たない場合

ここで、

\(X\) が \(Y\) と共通の整数を持たず、かつ \(|X| \geq 2\) であるときは -L と -R のみしか行えない

という追加ルールを課しても、本問題の最適解は変わりません。（証明は本解説の末尾に記載）

この追加ルールを課すと、入力で与えられた \(X\) を \(Y\) に一致させる手順は、

1. まず、\(X\) の長さが \(1\) になるまで -L または -R を繰り返す。
2. \(X\) が \(Y\) と共通の整数を持たない限り、下記の \((\ast)\) を繰り返す
   • +L か +R のどちらかを行った後、-L と -R のどちらかを行う \(\cdots (\ast)\)
3. +L と +R の繰り返しによって、\(X\) を \(Y\) と一致させる。

の形に限られます。1. と 3. の操作回数はそれぞれ \(|X|-1\) 回、\(|Y|-1\) 回に固定されるので、 2. での操作回数の最小化を考えます。

\(X\) は、\((\ast)\) を \(1\) 回行うたびに、ある長さ \(1\) の数列から別の長さ \(1\) の数列へと変化します。 異なる整数 \(u, v\) について、\(X = (u)\) の状態から \((\ast)\) を \(1\) 回行って \(X = (v)\) の状態に遷移できる必要十分条件は、

\(A\) が数列 \((u, v)\) または数列 \((v, u)\) を連続部分列として持つ

ことですが、これは

頂点集合が \(\lbrace 1, 2, \ldots, N \rbrace\) 、辺集合が \(\lbrace \lbrace A_i, A_{i+1} \rbrace : i = 1, 2, \ldots, N-1\rbrace\) である無向グラフ \(G\) 上で \(u\) と \(v\) が隣接している

ことと言い換えられます。

また、2. の開始時における \(X\) の唯一の要素は、1. でどれを残すかによって、 \(\mathcal{X} := \lbrace X_1, X_2, \ldots, X_P \rbrace\) の中から自由に選ぶことができ、 2. の終了時における \(X\) の唯一の要素は、 \(\mathcal{Y} := \lbrace Y_1, Y_2, \ldots, Y_Q \rbrace\) のどれであっても良いので、2. での操作回数の最小値は、\(G\) 上での

\[ D := \min \lbrace \mathrm{dist}(s, t) : s \in \mathcal{X}, t \in \mathcal{Y} \rbrace \]

を求める最短経路問題を解くことで、 \(2D\) 回と求まります。

追加ルールを課しても最適解が変わらないことの証明

\(op_1, op_2, \ldots, op_n\) を \(X\) を \(Y\) に一致させる最適な操作列とします。 「この操作列に追加ルールに抵触する操作があるかぎり、そのうち最後のものをその次の操作と入れ替える」ことを繰り返すと、追加ルールに抵触しない最適な操作列が得られることを以下で示します。

追加ルールに抵触する最後の操作が \(op_i = \) +R であったとします。 \(op_i\) の実行前の時点で \(X\) と \(Y\) は共通の整数を持たないため、\(op_i\) は最後の操作とはなり得ず、その次の操作 \(op_{i+1}\) が存在します。

• \(op_i\) で追加した整数が \(Y\) に含まれるとき、操作列の最適性から \(op_{i+1} = \) -L です。
• \(op_i\) で追加した整数が \(Y\) に含まれないときも、下記の理由よりやはり \(op_{i+1} = \) -L です。
  • \(op_{i+1} = \) -R だとすると、\(op_i\) と \(op_{i+1}\) を相殺することでより短い操作列が得られるので最適性に矛盾します。
  • \(op_{i+1} = \) +L または \(op_{i+1} = \) +R だとすると、\(op_{i+1}\) も追加ルールに抵触することになり、\(i\) の選び方に矛盾します。

\(op_{i}\) の実行前の時点で \(|X| \geq 2\) であるので、\(op_{i}\) = +R と \(op_{i+1}\) = -L を入れ替えて得られる操作列も実行可能で最適な操作列です。

\(op_i = \) +L の場合についても、上記と対称な議論が成り立ちます。

入れ替え後の操作列では入れ替え前の操作列と比較して、 \(1 \leq i \lt j \leq n\) かつ \(op_i =\) +L or +R かつ \(op_j = \) -L or -R を満たす整数の組 \((i, j)\) の個数が \(1\) 減少しています。 よって、この入れ替えの繰り返しは有限回で停止し、最終的に、追加ルールに抵触しない最適な操作列が得られます。