けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 185 E - Sequence Matching (水色, 500 点)

LCS (Longest Common Subsequence) によく似た DP!!

問題概要 (意訳)

長さ  N の整数列  A_{1}, \dots, A_{N} と、長さ  M の整数列  B_{1}, \dots, B_{M} が与えられる。これらに以下の操作を繰り返すことで、要素数が等しくなるようにしたい。

  • A の要素を 1 つ選んで削除する
  • B の要素を 1 つ選んで削除する

このとき、操作回数を  P として、 A_{i} \neq B_{i} となっているような  i の個数を  Q としたとき、操作のスコアは  P + Q で与えられる。この値の最小値を求めよ。

制約

  •  1 \le N, M \le 1000

考えたこと

二次元系列の DP は

などでとてもよく出てくる。そのような DP については、以下の記事の下の方で解説している!

qiita.com

今回も数列の「部分列」について扱う問題なので、同じような解法でできそうだ! (実は編集距離そのものだった)

  • dp[ i ][ j ] := A の最初の i 個分 (A[0 : i] と表す) と、B の最初の j 個分 (B[0 : j] と表す) のみを考えたときのスコア

とする。さて、このような二次元系列の DP の遷移を考えるときには、以下の 3 つの場合を考えるのが典型的。ここでは dp[ i ][ j ] へと集めていく DP を考えている。

  • A[0 : i] の末尾を削除する (dp[ i - 1 ][ j ] から遷移する)
    • chmin(dp[ i ][ j ], dp[ i - 1 ][ j ] + 1)
  • B[0 : j] 側の末尾を削除する (dp[ i ][ j - 1] から遷移する)
    • chmin(dp[ i ][ j ], dp[ i ][ j - 1 ] + 1)
  • A[0 : i] の末尾と B[0 : j] の末尾を対応させる
    • もし A[ i - 1 ] == B[ j - 1 ] ならば、chmin(dp[ i ][ j ], dp[ i - 1 ][ j - 1 ]
    • そうでないならば、chmin(dp[ i ][ j ], dp[ i - 1 ][ j - 1 ] + 1)

このように、A の末尾だけを削除するパターンと、B の末尾だけを削除するパターンと、A, B の末尾を対応させるパターンの 3 種類を考えると上手くいくことが多い!!

計算量は  O(NM) となる。

コード

#include <bits/stdc++.h>
using namespace std;
void chmin(int &a, int b) { if (a > b) a = b; }

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> A(N), B(M);
    for (int i = 0; i < N; ++i) cin >> A[i];
    for (int i = 0; i < M; ++i) cin >> B[i];

    const int INF = 1<<29;
    vector<vector<int>> dp(N+1, vector<int>(M+1, INF));
    dp[0][0] = 0;
    for (int i = 0; i <= N; ++i) {
        for (int j = 0; j <= M; ++j) {
            // A の末尾を削除
            if (i > 0) chmin(dp[i][j], dp[i-1][j] + 1);

            // B の末尾を削除
            if (j > 0) chmin(dp[i][j], dp[i][j-1] + 1);

            // A の末尾と B の末尾を対応させる
            if (i > 0 && j > 0) {
                if (A[i-1] == B[j-1]) chmin(dp[i][j], dp[i-1][j-1]);
                else chmin(dp[i][j], dp[i-1][j-1] + 1);
            }
        }
    }
    cout << dp[N][M] << endl;
}

編集距離

確かに完全に同じ問題ですね!

yukicoder.me