ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

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コード例を参考にしてください。

ACコード

Submission #67019853 - Codeforces

DPの更新順序について、 i, j が減ることはないですが、 k は増えたり減ったりするので注意です。 i, j は普通の2重ループで小さい方から順番に見ていって、

  • 遷移で  k を増やす(つまり ( を付ける)場合は、 k が小さい方から見ていく
  • 遷移で  k を減らす(つまり ) を付ける)場合は、 k が大きい方から見ていく

ようにすれば良いです。このようにしないと、例えば  i, j が一切変化しないまま ))))))... を付けて  k を大量に減らす、というような操作を見逃す可能性があります。