最適解の構造

\(2\) つ目の操作は、\(1\) つ目の操作が全て終わってから行うものとして良いです。

\(1\) つ目の操作を \(L\) 回行い、\(i\) 回目の操作では \(A\) の第 \(p_i\) 項と第 \((p_i+1)\) 項が入れ替えられるとします。このとき、全ての \(1\leq i < j\leq L\) について \(|p_i - p_j|\geq 2\) となるような最適解が存在します。言い換えると、\(A\) の各要素が高々 \(1\) 回しか入れ替えられないような最適解が存在します。また、この場合 \(1\) つ目の操作を行う順番をどのように選んでも最終的に得られる数列は変わりません。

従って、以下の動的計画法を考えることができます。

• \(dp(0,i)\) を、数列 \((A_1,\dots,A_i)\) を空にするのに必要な操作の合計回数の最小値とする。ただし、\(1\) つ目の操作で \(A_{i-1}\) と \(A_i\) は入れ替えない。

• \(dp(1,i)\) を、数列 \((A_1,\dots,A_i)\) を空にするのに必要な操作の合計回数の最小値とする。ただし、\(1\) つ目の操作で \(A_{i-1}\) と \(A_i\) を入れ替える。

全体の計算量は \(\mathrm{O}(N)\) です。

証明

\(A\) の各要素が高々 \(1\) 回しか入れ替えられないような最適解が存在することを証明します。

数列 \(p = (p_1,\dots,p_L)\) について、\(i\) 回目の操作で \(A\) の第 \(p_i\) 項と第 \((p_i+1)\) 項を入れ替えることで得られる数列を \(A(p)\) と表記します。また、数列 \(B = (B_1,\dots,B_N)\) について、\(2\) つ目の操作のみを使って \(B\) を空にするために必要な最小の操作回数を \(f(B)\) とします。\(f(B)-1\) は、\(B_i\neq B_{i+1}\) となる \(i\) の個数に等しいです。これらの表記を用いると、問題の答えは全ての数列 \(p\) に対する \(|p| + f(A(p))\) の最小値になります。ただし、\(|p|\) は \(p\) の長さです。

\(|p| + f(A(p))\) を最小にする \(p\) の中で、全ての \(1\leq i\lt j\leq |p|\) について \(|p_i-p_j|\geq 2\) となるものが存在することを示します。これを示すために、以下の補題を示します。

数列 \(p\) が、ある \(1\leq i\lt j\leq |p|\) について \(|p_i-p_j|\leq 1\) となるとき、ある数列 \(q\) が存在して \(|q|\lt |p|\) かつ \(|q| + f(A(q))\leq |p| + f(A(p))\) を満たす。

この補題が示せれば、\(|p| + f(A(p))\) を最小にする \(p\) の中で \(|p|\) が最小になるものを取ると、全ての \(1\leq i\lt j\leq |p|\) について \(|p_i-p_j|\geq 2\) となることが言えます。

補題の証明

補題の条件を満たす \(p\) を任意に取ります。ここで、頂点 \(1,\dots,N\) の \(N\) 頂点からなる無向グラフで、各 \(i\) \((1\leq i\leq |p|)\) について、頂点 \(p_i\) と \(p_{i+1}\) を結ぶ辺があるものを \(G(p)\) とします。ここで、\(G(p)\) は多重辺をもつ場合があることに注意してください。補題の仮定より、\(G(p)\) には \(3\) 頂点以上からなる連結成分が存在します。各連結成分に含まれる頂点の番号は区間になるので、この連結成分に含まれる頂点を \(x,x+1,\dots,x+{K-1}\) とします。ここで、\(K\geq 3\) が成り立ちます。また、異なる連結成分に対応する \(2\) つの操作は、行う順番を変えても最終的に得られる数列は変わらないため、\(x\leq p_i\leq x+K-2\) となる \(p\) の要素は全て \(p\) の末尾に集まっているものとしてよいです。すなわち、ある \(X\) が存在して

• 各 \(i\) \((1\leq i\leq |p|-X)\) について \(p_i\leq x-2\) または \(p_i\geq x+K\)
• 各 \(i\) \((|p|-X+1\leq i\leq |p|)\) について \(x\leq p_i\leq x+K-2\)

が満たされるとしてよいです。そして、\(p' = (p_1,\dots,p_{|p|-X})\) とします。このとき、\(G(p)\) における頂点 \(x,x+1,\dots,x+K-1\) の連結性より

\[ |p'|-|p| = -X \leq -K+1 \]

です。元の数列で \(A_x = A_{x+1} = \dots = A_{x+K-1}\) のときは \(A(p) = A(p')\) なので、\(q = p'\) とすれば補題の主張が従います。よって、後は \(A_x,A_{x+1}\dots ,A_{x+K-1}\) の中に相異なる要素が \(2\) つ以上ある場合を考えればよいです。

\(2\leq x\) かつ \(x+K-1\leq N-1\) の場合を考えます。\(B = A(p), B' = A(p')\) とすると、\(B\) と \(B'\) の違いは第 \(x\) 項から第 \(x+K-1\) 項のみなので、

\[ \begin{aligned} f(A(p')) - f(A(p)) &= f(B') - f(B)\\ &= \sum_{i=x-1}^{x+K-1}1_{B'_i\neq B'_{i+1}} - \sum_{i=x-1}^{x+K-1}1_{B_i\neq B_{i+1}}\\ &\leq (K+1) - 1\\ &= K \end{aligned} \]

となります。ここで、\(1_{B_i\neq B_{i+1}}\) は \(B_i\neq B_{i+1}\) のときに \(1\) を、そうでないときに \(0\) となる値で、\(1_{B'_i\neq B'_{i+1}}\) についても同様です。\(f(A(p')) - f(A(p))\leq K-1\) のときは \(|p'| + f(A(p'))\leq |p| + f(A(p))\) なので、\(q = p'\) とすれば補題の主張が従います。\(f(A(p')) - f(A(p)) = K\) のときは

\[ \sum_{i=x-1}^{x+K-1}1_{B'_i\neq B'_{i+1}} = K+1,~\sum_{i=x-1}^{x+K-1}1_{B_i\neq B_{i+1}} = 1 \]

の両方が成立します。よって、相異なる整数 \(\alpha,\beta\) が存在して

\[ \begin{aligned} (B'_{x-1},B'_x,\dots,B'_{x+K}) &= (\alpha,\beta,\alpha,\beta,\dots,\alpha,\beta)\\ (B_{x-1},B_x,\dots,B_{x+K}) &= (\alpha,\alpha,\dots,\alpha,\beta,\beta,\dots,\beta) \end{aligned} \]

と書けます。そこで、\(q\) を \(p'\) の末尾に \(x\) を加えた数列とすれば

\[ |q| - |p'| = 1,~ f(A(q))-f(A(p')) = -2 \]

となるので

\[ \begin{aligned} |q| + f(A(q)) - (|p| + f(A(p))) &= |q| + f(A(q)) - (|p'| + f(A(p'))) + |p'| + f(A(p')) - (|p| + f(A(p)))\\ &\leq -1 + (-K+1) + K\\ &= 0 \end{aligned} \]

です。さらに、\(K\geq 3\) より \(|q| - |p| = |p'| - |p| + 1\leq -K+2\leq -1\) なので、\(q\) は補題の主張を満たします。

\(x = 1\) や \(x+K-1 = N\) の場合は \(f(A(p')) - f(A(p))\leq K-1\) となるので、\(q = p'\) とすれば補題の主張が従います。

以上より、補題が示されました。