Insertion [AtCoder Beginner Contest 064 D]

http://abc064.contest.atcoder.jp/tasks/abc064_d

解法

http://abc064.contest.atcoder.jp/submissions/1341713
こういう括弧の問題は前から順に開いている括弧の個数を数え上げていく定石がある。
この定石を知らないと解くのは難しい。

先頭から開き括弧の個数を数えていくのだが、'('がくれば++, ')'がくれば--する。
この過程で開き括弧の個数がマイナスとなるなら、対応順がおかしくなっている（'('が足りない）し、最後に開き括弧の個数が0でないなら、これも対応順がおかしくなっている（')'が足りない）
この2つはどちらも先頭に'('をつける、後尾に')'をつけることで調整することができる。
辞書順で'('の方が先にくるため、つける'('は中途半端な部分ではなく、先頭に付けたほうが良い。
同様に、つける')'が中途半端な部分ではなく、後尾に付けた方が良い。

まず、先頭に'('をつけよう。
これは開き括弧の個数を数えていく中で、マイナスとなったときの絶対値の最大値が付ける個数になる。
これでまず付ける。

付けた後に改めて、開き括弧の個数を数え、最後の開き括弧の個数文だけ')'を付けて閉じると答えになる。

int N; string S;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> S;
    int cnt = 0, pre = 0;
    rep(i, 0, N) {
        if (S[i] == '(') cnt++;
        else {
            cnt--;
            if (cnt < 0) pre = max(pre, -cnt);
        }
    }
    rep(i, 0, pre) S = "(" + S;
    N += pre;
 
    cnt = 0;
    rep(i, 0, N) {
        if (S[i] == '(') cnt++;
        else cnt--;
    }
    rep(i, 0, cnt) S = S + ")";
 
    cout << S << endl;
}