AGC032 D - Rotation Sort

Posted on 3 mins read

D - Rotation Sort
知見の多い問題でした。

解法1

Editorialの方針とほぼ同じです。

左シフト、右シフトをそれぞれ任意箇所への挿入の操作に言い換えることが1つ目のポイント。
$i$に注目して$[i, j]$を左シフトすることで、$p_i$を右側の任意箇所に挿入することができます(同様に、右シフトは左側)。

さらに実数数直線上の好きな場所に移動させると考えると、1つの要素を2回以上させるメリットが無いため、1つの要素は1回以下の移動で良いことがわかります。

この実数数直線上で要素を小さい順に見ていき、開区間では以前より大きい要素が無限に取れるという性質を利用すると、
$$ \mathrm{dp}[i][k]: 要素iまでを[-1, k)に入るように動かしたときのコストの\min $$ というDPが回せます。

実数数直線上に拡張して半開区間で区切ってDPするというのは、任意箇所に挿入する操作を考えるときに比較的典型的なテクニックっぽいので覚えておきたい。

実装

signed main() {
  int n, a, b; cin >> n >> a >> b;
  vector<int> x(n);
  REP (i, n) {
    int p; cin >> p;
    p--;
    x[p] = i;
  }
  vector<vector<int>> dp(n + 1, vector<int>(n + 1, INF));
  REP (k, n + 1) dp[0][k] = 0;
  REP (i, n) {
    REP (k, n + 1) {
      if (k > 0) dp[i + 1][k] = dp[i + 1][k - 1];
      chmin(dp[i + 1][k], dp[i][k] + (x[i] <= k - 1 ? a : b));
      if (x[i] == k - 1) chmin(dp[i + 1][k], dp[i][k - 1]);
    }
  }
  cout << dp[n][n] << endl;
}

解法2

ながたかなさんののツイートを参考にしました。

はじめの操作の言い換えは同様です。

まずこの問題の特殊なケースとして、問題の操作でかかるコストを$f(p, A, B)$として$A = B = 1$の場合を考えてみましょう。
$p$のLIS (Longest Increasing Subsequence)の長さを$k$とすると、実は**$f(p, 1, 1) = |p| - k$**が成り立ちます。

  • $p$の$|p| - k$個の要素について、これらを適切な場所に挿入すれば単調増加になるため$f(p, 1, 1) <= |p| - k$は明らか
  • $k + 1$以上個の要素を固定してしまうとそれらは必ず単調増加にならないため、$f(p, 1, 1) >= |p| - k$

から、簡単に示せました。

さて、LISが $$ \mathrm{dp0}[i]: \max(p_iを末尾とする\mathrm{IS}の長さ) $$ を更新していくことで求められたことを思い出して、$f(p, 1, 1)$の値を直接求めようとすると、 $$ \mathrm{dp1}[i]: \min(i - p_iを末尾とする\mathrm{IS}の長さ) $$ になります。

ここまで来たら一般の$f(p, A, B)$に拡張できて、 $$ \mathrm{dp}[i]: \min(p_iまでで、p_iを末尾とする\mathrm{IS}以外を適切に動かしたときのコスト) $$ を求めればよいです。

これは$p$を左から見ていき、ISの1つ前となるような候補を、その他の要素を外に出すコストを累積しながら、逆から順番に見ていくことで$\mathcal{O}(n^2)$で計算することができます。

実装

signed main() {
  int n, a, b; cin >> n >> a >> b;
  vector<int> p(n + 2); REP (i, n) cin >> p[i + 1];
  p[n + 1] = n + 1;
  vector<int> dp(n + 2, INF);
  dp[0] = 0;
  REP (i, n + 2) {
    int acc = 0;
    for (int j = i - 1; j >= 0; j--) {
      if (p[j] > p[i]) {
        acc += a;
      } else {
        chmin(dp[p[i]], dp[p[j]] + acc);
        acc += b;
      }
    }
  }
  cout << dp.back() << endl;
}