AtCoder Beginner Contest 185 E - Sequence Matching

お題箱より。

解法

2つの数列や文字列を操作して一致させる問題では、前から1文字ずつ扱いを決めていくという方針のDPがうまくいく場合があります。特に2つの列の長さを $N, M$ として $O(NM)$ が間に合う場合はなおさらです。

このような問題の代表例として最長共通部分列（LCS）を求める問題が挙げられます。LCSを求めるDPは、

$dp\lbrack i \rbrack\lbrack j\rbrack =$ 列 $A$ の先頭 $i$ 文字と列 $B$ の先頭 $j$ 文字を見終わったときの、そこまでの共通部分列の長さの最大値

と状態を定義し、前から見ていきながら

の3通りの遷移で文字の扱いを決めていくものです。

共通部分列というのは結局のところ2つの列それぞれについて好きな箇所の要素を好きなだけ削除し、一致させたときの列と思うことができるので、今回の問題の前半部分と同じです。

LCSそのものの解説や具体的な遷移についてはこちらの記事などを参考にしてください。

今回の問題で最小化したい値 $x+y$ をコストと呼ぶことにします。今回の問題を少し言い換えると、

という2段階の操作によって2つの列を一致させる問題だと考えることができます。しかしこれを2段階の操作と見なさず、2つのコストを同時に処理していったほうがDPの枠組みで考えやすくなります。

LCSを求めるDPと同じように考え、状態を以下のように定義します。

$dp\lbrack i \rbrack\lbrack j\rbrack =$ 列 $A$ の先頭 $i$ 文字と列 $B$ の先頭 $j$ 文字を見終わったときの、そこまでの列を一致させるためのコストの最小値

遷移を次のように考えることで2つのコストを同時に処理していくことができます。

列 $A$ の今見ている文字を削除する。コストが $1$ 増える。
列 $B$ の今見ている文字を削除する。コストが $1$ 増える。
列 $A$ の今見ている文字と列 $B$ の今見ている文字が一致しているとき、その文字を共通列の次の文字として採用する。
列 $A$ の今見ている文字と列 $B$ の今見ている文字が異なっているとき、 $B$ の文字を変更して一致させた上で共通列の次の文字として採用する。コストが1増える。