問題概要 (意訳)

長さ $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 は

LCS (Longest Common Subsequence)
編集距離

などでとてもよく出てくる。そのような 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;
}