AtCoder Beginner Contest 185, E : Sequence Matching

問題文

　https://atcoder.jp/contests/abc185/tasks/abc185_e

問題概要

　長さ $N$ の正整数の列 $\{ A_i \}_{ i \in [ 0, N ) }$ と長さ $M $ の正整数の列 $\{ B_i \}_{ i \in [ 0, M ) }$ が与えられる．これらからいくつかの要素を取り除き（，残った要素を元々の順序を保ったまま連結することで），新たな列 $A', B'$ を作る．このとき，$| A' | = | B' |$ となるようにする（絶対値の記号で列の長さを表す）．
　ある取り除き方について，

• 取り除いた要素一つあたりコスト $1$
• $A'_i \neq B'_i$ なる $i$ 一つあたりコスト $1$

がかかる．すべての取り除き方の内，コスト最小なもののコストはいくらか？

制約

• $1 \leq N, M \leq 1{,}000$

解法

　$A, B$ を同時に先頭から眺めていって，各位置にある要素をどのように使うか（残す or 削除する）を決めていく探索を考えます．このとき，$A$ の先頭から $i$ 文字，$B$ の先頭から $j$ 文字は処理し終わったとして，次の要素の使い道を

• ともに残す．$A_i \neq A_j$ のときコスト $1$ ，そうでなければ $0$
• $A$ の要素を一つ捨てる（削除する）．コスト $1$
• $B$ の要素を一つ捨てる．コスト $1$

と分類すると網羅的になります．これをベースに次のように状態をとる動的計画法を考えることができます：

• $\mathit{ dp }_{ i, j } :=$ $A$ の先頭から $i$ 要素，$B$ の先頭から $j$ 要素の使い道が決まったときのコストの最小値

遷移としては上述した「次の要素の使い道」3 通りがそのまま対応します．テーブルを計算し終わったあと，$\mathit{ dp }_{ N, M }$ を読むと答えが求まっています．
　この DP の状態数（DP テーブルのサイズ）は明らかに $\Theta( N M )$ で，各状態からの遷移は O$( 1 )$ 個で，どの遷移も $O( 1 )$ 時間で計算（$\min$ の計算及び $\min$ に入れる値の計算）できます．よって，全体の計算量は $O( N M )$ 時間となります．

コード

constexpr auto INF = LIM<>::max() / 2;

int main()
{
	IN( int, N, M );
	VI A( N ), B( M );
	cin >> A >> B;

	static int dp[ 1024 ][ 1024 ];
	fill( AALL( dp ), INF );
	dp[0][0] = 0;

	REP( i, N + 1 )
	{
		REP( j, M + 1 )
		{
			if ( i < N && j < M )
			{
				chmin( dp[ i + 1 ][ j + 1 ], dp[i][j] + ( A[i] != B[j] ) );
			}
			if ( i < N )
			{
				chmin( dp[ i + 1 ][j], dp[i][j] + 1 );
			}
			if ( j < M )
			{
				chmin( dp[i][ j + 1 ], dp[i][j] + 1 );
			}
		}
	}

	cout << dp[N][M] << endl;

	return 0;
}