【AOJ】AOJ 3204 - そこそこバランスのとれた括弧列

模擬国内2020D

公式解説以上の情報はありません。

解説?

普通の括弧列の場合は ( に +1 を、) に -1 を割り当てて、総和を 0 に、prefix sum が常に 0 以上となるかを判定する。今回は、 ( に +2 を、) に -2 を原則割り当てるが、連続する 2 つの ( の組は +1+1 に、連続する 2 つの ) の組は -1-1 に割り当てることもでき、複数の組に同じ括弧を対応付けてはならないとして、同様の条件を満たすかを判定する問題である。

まず、必要な ) の個数について考える。

) は末尾に付けるだけで良い。なぜなら、付ける位置によらず全体の総和は不変であり、かつ prefix sum への影響を考えると、末尾以外の部分に付いているものを末尾に付けても損しないためである。

) を末尾に付けるとして、必要な ) の個数は、前から文字列を見ていき

( が出てきたらスタックにプッシュする
) が出てきたら可能な限り 2 つの ( に対応させる（インデックスも保存すれば簡単に判定可能）

上記のような貪欲法を行い、残った ( に ) を対応させることで、必要な ) の個数の下界が分かる。（提出コードのほうがわかりやすいかも。）

次に、必要な ( の個数について考えると、) の場合と同じことを文字列を反転させて行えば良い。

( の個数と ) の個数は独立に考えて良いため、この個数の和が答えの下界になる。

そして、この下界が実際に達成できることが証明できる。

らしいが、証明の仕方が分かりませんでした！いかがでしたか？

#include <bits/stdc++.h>
using namespace std;

#define REP(i, n) for (int i = 0; i < (n); i++)

void solve(string S) {
    int N = int(S.size());
    int ans = 0;
    REP(_, 2) {
        vector<pair<char, int>> T;
        REP(i, N) {
            if (S[i] == '(') {
                T.emplace_back('(', i);
            } else {
                int M = int(T.size());
                if (M >= 2 and T[M - 2].first == '(' and T[M - 1].first == '(' and T[M - 2].second + 1 == T[M - 1].second) {
                    T.pop_back();
                    T.pop_back();
                } else if (M >= 1 and T.back().first == '(') {
                    T.pop_back();
                } else {
                    T.emplace_back(')', i);
                }
            }
        }
        while (T.size() > 0 and T.back().first == '(') {
            int M = int(T.size());
            if (M >= 2 and T[M - 2].first == '(' and T[M - 1].first == '(' and T[M - 2].second + 1 == T[M - 1].second) {
                T.pop_back();
                T.pop_back();
                ans++;
            } else if (T.back().first == '(') {
                T.pop_back();
                ans++;
            } else {
                assert(0);
            }
        }
        string NS;
        REP(i, N) NS += S[N - 1 - i] == '(' ? ')' : '(';
        S = NS;
    }
    cout << ans << '\n';
}

int main() {
    string S;
    while (cin >> S, S != "#") solve(S);
    return 0;
}