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

問題リンク
codeforces.com

問題概要
文字からなる文字列が与えられるので, を（連続でなくてもよい）部分列として含むような最小文字数の正規括弧列を出力する.

正規括弧列の定義は次の通り
1. 空文字
2. ある正規括弧列が存在して, '(' A ')' のこの順に連結したもの
3. ある空でない正規括弧列が存在して, A Bのこの順に連結したもの

考えたこと（解法）

次の動的計画法を考える.
dp[i][j][k] := 文字列sのi番目及び, 文字列tのj番目まで確定しており, 余分なopenがk個あるとき(言い換えるとcloseをk個置ける)の最小文字数

いま文字列sのi番目と文字列tのj番目を見ているとき今置こうとする文字(open, close)と合致していれば, (i, j, k)の値を更新する.
kが0の場合, closeはおけないことに注意する.

以上のアプローチから最小文字数は求められるが, 復元をする必要がある.

値と状態からfor文で適当に復元をしたらWAになったのでmapで状態の遷移を持ってやった. これだと普通に遅いので, ここは練習がいると感じた.

提出コード
codeforces.com