【AtCoder】ABC 185 E - Sequence Matching

2026-11-07

AtCoder/ABC/E問題 AtCoder/ABC/500点問題 AtCoder/水Diff AtCoder/NoviSteps/1Q AtCoder/動的計画法/編集距離競技プログラミング

E - Sequence Matching

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

AtCoder

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 1468 / NoviSteps: 1Q / 配点: 500 点

問題概要

長さ $N$ の整数列 $A$ と、長さ $M$ の整数列 $B$ がある。

高橋君は $A$ からいくつかの要素を取り除き、残った要素をそのままの順番で繋げることで新たな数列 $A'$ を作る(一つも取り除かなくても、全部取り除いても構わない)。 $B$ についても同様に、いくつかの要素を取り除き、残った要素をそのままの順番で繋げることで新たな数列 $B'$ を作る(一つも取り除かなくても、全部取り除いても構わない)。このとき、 $|A'| = |B'|$ となるような取り除き方をする。

$A, B$ から取り除いた合計要素数を $x$ とし、 $1 \le i \le |A'|$ かつ ${A'}_i \neq {B'}_i$ を満たす整数 $i$ の数を $y$ とするとき、 $x + y$ として考えられる最小の値を求めよ。

制約

$1 \le N, M \le 1000$
$1 \le A_i, B_i \le 10^9$
入力は全て整数

考察

問題文が分かりにくいが、 $A$ を $B$ へ一致させるための操作回数を求める問題であると考えると、理解しやすい。いわゆる「編集距離」の問題である。

具体的には、以下のようになる。

$A$ の要素を削除する → 削除
$B$ の要素を削除する → 挿入
$A$ と $B$ の対応する要素が異なる → 置換

したがって、

\mathrm{dp}_{i, j} = A\text{の先頭}i\text{文字と}B\text{の先頭}j\text{文字との編集距離}

と定義すると、先ほどの3つの操作それぞれに対する漸化式は

$A$ の要素を削除する: $\mathrm{dp}_{i, j} = \mathrm{dp}_{i - 1, j} + 1$
$B$ の要素を削除する: $\mathrm{dp}_{i, j} = \mathrm{dp}_{i, j - 1} + 1$
$A$ と $B$ の対応する要素が異なる: $\mathrm{dp}_{i, j} = \mathrm{dp}_{i - 1, j - 1} + 1\left[ A_i \neq B_j \right]$

となるから、これらを組み合わせると、

\mathrm{dp}_{i, j} = \min\left( \mathrm{dp}_{i - 1, j} + 1, \mathrm{dp}_{i, j - 1} + 1, \mathrm{dp}_{i - 1, j - 1} + 1\left[ A_i \neq B_j \right] \right)

となる。

また、初期値は $\mathrm{dp}_{i, 0} = i, \: \mathrm{dp}_{0, j}=j$ で、最終的な答えは $\mathrm{dp}_{N, M}$ とすればよい。

計算量は $O(NM)$ である。

実装例

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
5. 
6.constexpr int INF = 1e+9;
7. 
8.// ======================================== //
9. 
10.int main()
11.{
12.    int N, M;
13.    cin >> N >> M;
14.    vector<int> A(N), B(M);
15.    rep(i, 0, N) cin >> A[i];
16.    rep(i, 0, M) cin >> B[i];
17. 
18.    vector<vector<int>> dp(N + 1, vector<int>(M + 1, INF));
19.    rep(i, 0, N + 1) dp[i][0] = i;
20.    rep(j, 0, M + 1) dp[0][j] = j;
21. 
22.    rep(i, 1, N + 1) rep(j, 1, M + 1)
23.    {
24.        dp[i][j] = min({
25.            dp[i - 1][j] + 1,
26.            dp[i][j - 1] + 1,
27.            dp[i - 1][j - 1] + (A[i - 1] != B[j - 1])
28.            });
29.    }
30. 
31.    cout << dp[N][M] << endl;
32. 
33.    return 0;
34.}