D - Pure Straight Editorial
by 
maspy
◆ 使う項と部分列の位置を固定した場合
まずは、使用する項 \(A_{i_1}, \ldots, A_{i_K}\) (\(i_1 < \cdots < i_K\))と、連続部分列 \((1, 2, \ldots, K)\) を作る位置 \(j_1, \ldots, j_K = n, n+1, \ldots, n+K-1\) を固定した上で、最小操作回数について考えます。
添字が昇順に並んだ列 \(I = (i_1, \ldots, I_K)\), \(J = (j_1, \ldots, j_K)\) に対して、その距離を \(\sum_{k=1}^K |i_k - j_k|\) により定めます。また、列 \((x_1, \ldots, x_K)\) の転倒数 \(\text{inv}(x_1, \ldots, x_K)\) を、\(i<j\) かつ \(x_i>x_j\) となる組 \((i,j)\) の個数として定めます。
\(A_{i_1}, \ldots, A_{i_K}\) を位置 \(j_1, \ldots, j_K = n, n+1, \ldots, n+K-1\) に昇順並べるために必要な最小操作回数が、\(\text{dist}(I, J) + \text{inv}(A_{i_1}, \ldots, A_{i_K})\) であることを示すことができます。
実際、
- 注目している \(K\) 項の間を入れ替える場合：転倒数は高々 \(1\) 減少。\(I, J\) の距離は変化しない。
- そうでない隣接互換：\(\text{dist}(I,J)\) は高々 \(1\) 減少、転倒数は変化しない。
が成り立つため、少なくとも \(\text{dist}(I, J) + \text{inv}(A_{i_1}, \ldots, A_{i_K})\) 以上の操作回数が必要です。逆に、各 \(A_{i_k}\) を位置 \(j_k\) に移動させたあとで、これら \(K\) 項の間の隣接互換を繰り返すことで、\(\text{dist}(I, J) + \text{inv}(A_{i_1}, \ldots, A_{i_K})\) 回の操作により目的を達成することができます。
◆ 使う項のみを固定した場合
次に、使う項のみを固定した場合の最小操作回数を計算する方法を考えます。これには、連続部分列 \((1, 2, \ldots, K)\) を作る位置 \(j_1, \ldots, j_K = n, n+1, \ldots, n+K-1\) を選んで、\(\sum |i_k - j_k|\) を最小化すればよいです。
\(m = \lceil K/2\rceil\) とするとき、次が確かめられます。
\(i_m < j_m\) ならば、\(j_1, \ldots, j_K\) をすべて \(1\) 減少させると、\(1\leq k\leq m\) のときに \(|i_k - j_k|\) は \(1\) 減少する。\(m < k\leq K\) のときに \(|i_k - j_k|\) は高々 \(1\) 増加する。
\(i_m > j_m\) ならば、\(j_1, \ldots, j_K\) をすべて \(1\) 増加させると、\(1\leq k< m\) のときに \(|i_k - j_k|\) は高々 \(1\) 増加する。\(m \leq k\leq K\) のときに \(|i_k - j_k|\) は\(1\) 減少する。
これらから、\(i_m = j_m\) であるような最適解が存在することが分かります。このとき、
- \(1 < k < m\) ならば \(|i_k - j_k| = j_k - i_k = (j_m + k-m) - i_k\)
- \(m< k \leq K\) ならば \(|i_k - j_k| = i_k - j_k = i_k - (j_m + k - m)\)
となるため、\(\text{dist}(I, J)\) は \(i_1, \ldots, i_K\) の式として \(\sum a_ki_k + b\) (\(a_k\in \{-1,0,1\}\)) の形に計算可能です。この値に \((A_{i_1},\ldots, A_{i_K})\) の転倒数を加えたものが、\((A_{i_1},\ldots, A_{i_K})\) を使う場合の最小操作回数となります。
◆ DP による計算
\(A_{i_1}, \ldots, A_{i_K}\) を選んだ場合の最小操作回数は、定数の差を除いて
- \(i_k\) の線形結合 \(\sum_{k=1}^K a_ki_k\)
- \((A_{i_1}, \ldots, A_{i_K})\) の転倒数
の和として計算できるのでした。特に、\(0\leq K'\leq K\) に対して、「\((A_{i_1}, \ldots, A_{i_{K'}})\) まで定めたときのコスト」が
- \(i_k\) の線形結合 \(\sum_{k=1}^{K'} a_ki_k\)
- \((A_{i_1}, \ldots, A_{i_{K'}})\) の転倒数
の和として定義できます。選んだ \(K'\) 項が集合として \(S\) に等しい場合の最小コストを \(\text{dp}[S]\) とする DP により本問題を解くことができます。 時間計算量は \(O(2^KN)\) です。
◆ 解答例
なお、本問題には DP を用いない解法もあり、その計算量も多岐にわたります。例えば以下の解答例の後者は、計算量 \(\Theta(N^2+2^KK^{1.5}N)\) の解法となっています。
posted:
last update: