Educational Codeforces Round 83: E. Array Shrinking

競技プログラミング 動的計画法 区間DP Codeforces

問題

問題文

問題概要

項数 (1 \leq n \leq 500) の数列 a が与えられる.

a_i = a_{i+1} を満たす組を選び, a_i + 1 に置き換えるという操作をできるだけした際, 最終的な数列の長さとして考えられるもののうち最小のものを答えよ.

例

4 3 2 2 3 -> 4 3 3 3 -> 4 4 3 -> 5 3

the answer is 2.

解答例

指針

解説

すべての区間について, ひとつの要素に置き換えることができるかどうかを調べる事を考える.

例えば, a = \{ 4, 3, 2, 2, 3 \} ならば, 区間 [2, 3], [2, 3, 4], [1, 2, 3], [0, 1, 2, 3] は 1つの要素に置き換え可能である.

ここで, dp[l][r] を以下のように定義する.

dp[l][r] := x \\\\ (\text{半開区間 [l, r) の数列を数字xに置き換え可能, 無理ならx =-1})

もし, 区間 [l, r) を1つの要素に置き換え可能ならば, 区間 dp[l, mid) = dp[mid, r), を満たす, l, mid, r が存在するか, もしくは区間の長さが1となる.

実際, a = \{ 4, 3, 2, 2, 3 \} のとき, 要素 \{ 4, 3, 2, 2 \}, を含む区間 [0, 4) は1つの要素 5 に置き換え可能であるから, dp[0][4] = 5 となり, このとき, 以下のように区間の長さが短いものから計算していくと, dp[2][4] = 3, dp[1][4] = 4 なので dp[0][1] = dp[1][4] = 4 となる.

dp配列を更新するときは, 以下のように, 区間の長さが短いものから更新していく.

  vector<vector<int>> dp(n+1, vector<int>(n+1,-1));
  for (int i = 0; i < n; i++) {
    dp[i][i+1] = a[i];
  }

  for (int len = 2; len <= n; len++) {
    for (int l = 0; l + len <= n; l++) {
      int r = l + len;
      for (int mid = l+1; mid < r; mid++) {
        if (dp[l][mid] != -1 && dp[l][mid] == dp[mid][r]) {
          dp[l][r] = dp[l][mid] + 1;
        }
      }
    }
  }

次に, 数列のi番目まで見たとき, 置き換えの操作をできるだけ行った後の数列の長さの最小値を考える.

ここで, dp2[len] を以下のように定義する.

dp2[\text{len}] := \text{数列の先頭からlen番目までを見たとき, 置き換え操作をできるだけ行ったあとの数列の長さの最小値}

このとき, dp2[n] が問題の答えとなる.

dp2配列の更新は, 以下のように dp[j][i] が -1 でないとき, すなわち 区間 [j, i) が1つの要素に置き換え可能なら, dp2[i] = min(dp2[i], dp2[j] + 1); とすればよい.

  vector<int> dp2(n+1);
  for (int i = 1; i <= n; i++) {
    dp2[i] = i;
    for (int j = 0; j < i; j++) {
      if (dp[j][i] != -1) {
        dp2[i] = min(dp2[i], dp2[j] + 1);
      }
    }
  }

全体の計算量は dp配列の更新が支配的となり, O(n^{3}).

実装例

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
 
using namespace std;
 
int main() {
  int n; cin >> n;
  vector<int> a(n);
 
  for (int i = 0; i < n; i++) { scanf("%d", &a[i]); }
 
  vector<vector<int>> dp(n+1, vector<int>(n+1,-1));
  for (int i = 0; i < n; i++) {
    dp[i][i+1] = a[i];
  }
 
  for (int len = 2; len <= n; len++) {
    for (int l = 0; l + len <= n; l++) {
      int r = l + len;
      for (int mid = l+1; mid < r; mid++) {
        if (dp[l][mid] != -1 && dp[l][mid] == dp[mid][r]) {
          dp[l][r] = dp[l][mid] + 1;
        }
      }
    }
  }
 
  vector<int> dp2(n+1);
  for (int i = 0; i <= n; i++) {
    dp2[i] = i;
    for (int j = 0; j < i; j++) {
      if (dp[j][i] != -1) {
        dp2[i] = min(dp2[i], dp2[j] + 1);
      }
    }
  }
  cout << dp2[n] << endl;
  return 0;
}
  • Python3
n = int(input())
a = [ int(x) for x in input().split() ]
 
dp = [ [-1] * (n+1) for _ in range(n+1) ]
for i in range(n):
    dp[i][i+1] = a[i]
 
for leng in range(2, n+1):
    for l in range(n+1):
        if l + leng > n: continue
        r = l + leng
        for mid in range(l+1, n+1):
            if dp[l][mid] != -1 and dp[l][mid] == dp[mid][r]:
                dp[l][r] = dp[l][mid] + 1
 
dp2 = [ float("inf") for _ in range(n+1) ]
for i in range(n+1):
    dp2[i] = i
    for j in range(i):
        if dp[j][i] != -1:
            dp2[i] = min(dp2[i], dp2[j] + 1)
 
print(dp2[n])

参考文献