問題概要

2つの括弧列 $ s,t (\left| s \right|, \left| t \right| \leq 200) $ が与えられる．

$ s, t $ の両方を部分文字列としてもつ regular な (括弧の対応が取れている) 括弧列で，長さが最も短いものを1つ答えよ．

解法概要

$ \left| s \right|, \left| t \right| $ が 200 以下と小さいので，それぞれ何文字目まで見たかのポインタを持って DP する．

ただし，2つのポインタを持つだけでは状態の区別が不十分．例えば，$ s = $ ), $ t = $ )) のような場合を考えてみる．この場合の答えは (()) であるが，( は $ \left| s \right|, \left| t \right| $ には一度も登場しない．したがって，「ポインタは進めないが，括弧列が対応を取れるようにするための括弧を挿入する」という事態が発生する．このような事態が起きても正しい括弧列とそうでない括弧列を区別したり，正しい括弧列にするためにどれだけ括弧を挿入する必要があるかの情報を持つためには，2つのポインタに加えて「現地点での ( と ) の数の偏り」も状態として持っておく必要がある．

これは単に ( の数から ) の数を引いたものを持っておけばよい．この値の取りうる範囲を考える．まず，0未満になることはあり得ない．なぜならば，括弧列を左から見て行ったとき， ) の数が ( の数を上回ってしまった地点でその括弧列は対応が取れないからである．また，200を超えることもあり得ない．$ \left| s \right|, \left| t \right| \leq 200 $ より，答えとなる括弧列の長さはせいぜい 400 であるため， ( の数から ) の数を引いた値が 200 を超えてしまうとその地点でつじつまを合わせることが不可能になってしまうからだ．

次に今の状態を「$ s $ を $ i $ 文字見て，$ t $ を $ j $ 文字見て， ( の数から ) の数を引いた左は $ k $ 」として，$ s_i, t_j, k $ の値で場合分けして遷移を考える．この遷移はソースコード参照．

遷移の実装は再帰，多重ループなど様々な方針が考えられる．しかし今回は1回の遷移で必ず1文字だけ追加するということと，各状態を訪れる順番が非自明であることから， BFS のようにして実装するのが楽であると考えられる．

ソースコード

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <tuple>

using namespace std;

constexpr int INF = 1 << 30;

struct State {
    int i, j, k;
    State(int i=INF, int j=INF, int k=INF): i(i), j(j), k(k) {}
};

int length[201][201][210];
State prev_state[201][201][210];
queue<State> que;

void update(int i0, int j0, int k0, int i1, int j1, int k1) {
    if(k1 < 0 || k1 > 200) return;
    if(length[i1][j1][k1] > length[i0][j0][k0] + 1) {
        length[i1][j1][k1] = length[i0][j0][k0] + 1;
        prev_state[i1][j1][k1] = State(i0, j0, k0);
        que.push(State(i1, j1, k1));
    }
}

int main() {
    string s, t;
    cin >> s;
    cin >> t;
    int n = s.length(), m = t.length();
    fill_n(length[0][0], 201*201*210, INF);

    que.push(State(0, 0, 0));
    length[0][0][0] = 0;
    while(!que.empty()) {
        State state = que.front(); que.pop();
        int i = state.i, j = state.j, k = state.k;

        if(i == n && j == m) {
            if(k == 0) break;
            else update(n, m, k, n, m, k-1);
            continue;
        }
        
        if(i == n) {
            if(t[j] == '(') {
                update(n, j, k, n, j+1, k+1);
                update(n, j, k, n, j, k-1);
            } else {
                update(n, j, k, n, j, k+1);
                update(n, j, k, n, j+1, k-1);
            }
        } else if(j == m) {
            if(s[i] == '(') {
                update(i, m, k, i+1, m, k+1);
                update(i, m, k, i, m, k-1);
            } else {
                update(i, m, k, i, m, k+1);
                update(i, m, k, i+1, m, k-1);
            }
        } else {
            if(s[i] == '(') {
                if(t[j] == '(') {
                    update(i, j, k, i+1, j+1, k+1);
                    update(i, j, k, i, j, k-1);
                } else {
                    update(i, j, k, i+1, j, k+1);
                    update(i, j, k, i, j+1, k-1);
                }
            } else {
                if(t[j] == '(') {
                    update(i, j, k, i, j+1, k+1);
                    update(i ,j, k, i+1, j, k-1);
                } else {
                    update(i, j, k, i, j, k+1);
                    update(i, j, k, i+1, j+1, k-1);
                }
            }
        }
    }

    string ans = "";
    int i = n, j = m, k = 0;
    while(prev_state[i][j][k].i != INF) {
        if(prev_state[i][j][k].k < k) {
            ans += '(';
        } else {
            ans += ')';
        }
        tie(i, j, k) = {prev_state[i][j][k].i, prev_state[i][j][k].j, prev_state[i][j][k].k};
    }
    reverse(ans.begin(), ans.end());

    cout << ans << endl;
}

所感

括弧列の問題すき

問題文の "regular" を簡潔にわかりやすく訳せる日本語ってあるのかなあ

NoiminのNoise

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

問題概要

解法概要

ソースコード

所感