Codeforces Round #605 (Div. 3) F. Two Bracket Sequences

お題箱より。

Problem - F - Codeforces

問題概要

カッコ列 $S, T$ が与えられる。「正しい」カッコ列であって、 $S, T$ の両方を部分列として含むようなカッコ列のうち、長さが最小のものを1つ求めよ。

制約

$1 \le |S|, |T| \le 200$

解法

文字列のインデックスは0-indexedで表記します。

まずは正しいカッコ列にこだわらず、「文字列 $S, T$ の両方を部分列として含むような長さ最小の文字列」を求めることを考えます。これは最長共通部分列（LCS）として知られるものとよく似たDPで解くことができます。

$dp\lbrack i \rbrack\lbrack j \rbrack$ ：文字列 $S$ の $i-1$ 文字目までと文字列 $T$ の $j-1$ 文字目までの両方を部分列として含む、長さ最小の文字列の長さ

このDPの $dp\lbrack i \rbrack\lbrack j \rbrack$ からの遷移は以下の3通りです。

$S$ の $i$ 文字目を末尾に付ける。長さを $1$ 足して $dp\lbrack i+1 \rbrack\lbrack j \rbrack$ に遷移する。
$T$ の $j$ 文字目を末尾に付ける。長さを $1$ 足して $dp\lbrack i \rbrack\lbrack j+1 \rbrack$ に遷移する。
$S$ の $i$ 文字目と $T$ の $j$ 文字目が等しい場合、その文字を末尾に付ける。長さを $1$ 足して $dp\lbrack i+1 \rbrack\lbrack j+1 \rbrack$ に遷移する。

カッコ列についても、これと似たようなことをします。こちらは「正しい」カッコ列でなければならないという条件があるので、これまでの $(開きカッコの数)-(閉じカッコの数)$ を持っておくことにします。これを「深さ」と呼ぶことにします。

$dp\lbrack i \rbrack\lbrack j \rbrack\lbrack k \rbrack$ ：カッコ列 $S$ の $i-1$ 文字目までとカッコ列 $T$ の $j-1$ 文字目までの両方を部分列として含み、深さが $k$ であるもののうち、長さ最小のカッコ列の長さ

遷移は末尾に開きカッコを付ける場合と閉じカッコを付ける場合の2通りを考え、それぞれ文字を付けた時に $S, T$ の添字が進むかどうかをチェックすれば良いです。 $k \lt 0$ の範囲には遷移しません。

このDPの添字として扱うべき範囲を考えましょう。 $i$ の最大値は $|S|$ 、 $j$ の最大値は $|T|$ なので $200$ 以下です。 $k$ として扱うべき値の範囲を考えます。

ここで () が $200$ 個続くような文字列 ()()()......() は必ず条件を満たすことに注目します。つまり答えは必ず $400$ 以下です。もしDPの遷移の途中で $k$ が $200$ を超えた場合、その開きカッコを全て閉じる必要があるので文字列の長さは必ず $400$ を超えます。そのため、 $k$ としても $200$ 以下の範囲だけを考えれば良いです。

状態数が $201^{3}$ で各遷移が $2$ 通りなので、十分間に合います。答えとなる文字列の長さは $dp\lbrack |S| \rbrack\lbrack |T| \rbrack\lbrack 0 \rbrack$ として求められますが、実際の文字列を求める必要があるので、地道に各添字の組について遷移元の添字の組を持っておいて復元しましょう。具体的にはACコード例を参考にしてください。