Codeforces Round #605 (Div. 3) - F. Two Bracket Sequences - Senの競技プログラミング備忘録

概要

'('と')'のみが含まれる文字列S, Tが与えられる。次の条件を満たす文字列Xを構成してください。

SとTはどちらもXの部分文字列である。
Xはかっこ列としてすべての'(' と ')' は対応されていて、かつその2文字からのみ成る。
Xの長さはありうるものすべての中で最小である。この時いくつかの候補があるのならば、そのどれを出力してもよい。

制約
1 <= S.size(), T.size() <= 200

ACするまで

1. ()列であることを考えずに、共通部分列の要領でDPをやってみる。->いける！
2. ()列DPの典型で、DPの添え字にかっこ列の深さを追加してDPする。
3. かっこ列の深さが途中で0以上でないといけないというルールでは、S = ")", T = ")))" のようなときにはDPできない。(()の深さを考えずに文字列Xを作るならば、使用する文字は必ずSとTのうちのいずれかに含まれないといけないが、今回の場合は正しいかっこ列を作らないといけないので、SとTに含まれてないものも使用する可能性がある)
4. DPをしながら、新しい状態の遷移の元をメモする。そして最後に復元
5. AC!

考察

ひとまず、()列として正しいかどうかを無視して、SとTを部分文字列として含む最短の文字列Xを構築してみる。
次のように定める。

int dp[MAX_S][MAX_T] = {};
//dp[i][j] := 1-idxでSのi番目とTのj番目まで考えた時の文字列Xの長さ

そして、遷移はつぎのようになる。

//dp[i][j]はdp[0][0] = 0, 以外すべてINF埋めされてるものとする。

if(i + 1 < S.size() && j + 1 < T.size() && S[i] == T[j]){
    //S[i]とT[j]が同じなら、今のdp[i][j]にS[i]をつける(長さを1増やす)ことで、dp[i + 1][j + 1]を更新できる。
    dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + 1);
}
else if(i + 1 < S.size()){
    //S[i]を後ろにくっつけることで、dp[i][j] + 1でdp[i + 1][j]を更新できる。
    dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + 1);
}
else if(j + 1 < T.size()){
    //T[j]を後ろにくっつけることで、dp[i][j] + 1でdp[i][j + 1]を更新できる。
    dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + 1);
}
//答えは dp[S.size()][T.size()];

これから発展して、かっこ列の深さというのを添え字に追加で持った時を考える。
ACするまでの3番にも書いてあるように、単純に最短の文字列Xを作るのと、かっこ列を成立させるうえで最短の文字列Xにするには次のような違いがある。

単純に最短なら、dp[i][j]から次へ遷移するとき、後尾に追加する予定の文字列はS[i]もしくはT[j]のいずれかである。
()の深さを添え字に入れて考えると、かならずしもS[i]とT[j]のいずれかを次へ遷移するときに入れる必要はない。(もちろんその分Xの文字数は増えることになるが)

なぜならば、
S[i] == T[j] == '('で現時点での深さが0の時に、そのままやると深さは-1になってしまうため、一旦S[i]でもT[i]でもない'('を入れるということをやるためです。なんの制約もない場合で文字列Xを生成するには無駄な文字を入れる操作でも、ほかに制約ができた時には無駄でなくなる場合がある。

このことを踏まえると、

int dp[i][j][k];//dp[i][j][k] := 1-idxでSのi番目とTのj番目まで考えて、()列の深さがkの時の文字列Xの長さ

として、上と似たような遷移になる。(詳しくはソースコード参照)

また、この問題は経路復元を要求されるが、メモリを食うけど実装的には楽な方法で復元することを勧める。これはつぎのような方法である。

#include<tuple>

typedef tuple<int, int, int> T3;

int dp[MAX_S][MAX_T][MAX_S + MAX_T];
T3 resolve[MAX_S][MAX_T][<MAX_S + MAX_T];
//resolveは復元配列　resolve[i][j][k]に入れるtupleは、resolveを更新した際の更新先を入れてる

int ni, nj, nk;//遷移先のi, j, k

if(dp[ni][nj][nk]が更新されるなら){
    dp[ni][nj][nk] = dp[i][j][k] + 114514;
    resolve[ni][nj][nk] = make_tuple(i, j, k);
}

そして、復元する際には次のようにする。

int int_i = 0, int_j = 0, int_k = 0;//dpを始めるときの初期状態
int i, j, k;//最後の答えになってるdp[i][j][k]の添え字

vector<int> anslist;//経路

while(true){
    if(int_i == i && int_j == j && int_k == k){
        break;
    }
    int bi = get<0>(resolve[i][j][k]);
    int bj = get<1>(resolve[i][j][k]);
    int bk = get<2>(resolve[i][j][k]);
    //bi, bj, bkとどこから来たのかからanslistに経路を追加する。
    i = bi, j = bj, k = bk;
}
//最後、anslistは後ろから前の順番になってるので、std::reverse()を使って戻すこと
reverse(anslist.begin(), anslist.end());