括弧を語る数 / Parentheses Number Ritsumeikan University Competitive Programming Camp 2019 Day 3 B]

https://onlinejudge.u-aizu.ac.jp/services/room.html#RitsCamp19Day3/problems/B

解説

https://onlinejudge.u-aizu.ac.jp/services/review.html#RitsCamp19Day3/3419433

貪欲に構築していこう。
)を入れる前に(の数が足りない場合は、その分入れる。
足りてる場合は、とりあえず)を入れる。
この段階で大丈夫かチェックしてもいいが、自分は構築後に確認している。
構築できない場合があるような問題は、最後になるべくチェックするといい。

int N, P[101010], A[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> P[i];

    string ans = "";
    int cnt = 0;
    rep(i, 0, N) {
        while (cnt < P[i]) {
            ans += "(";
            cnt++;
        }
        ans += ")";
    }

    stack<int> stk;
    int st = 1;
    int idx = 0;
    rep(i, 0, N * 2) {
        if (ans[i] == '(') {
            stk.push(st);
            st++;
        }
        else {
            if (stk.size() == 0) {
                printf(":(\n");
                return;
            }

            A[idx] = stk.top();
            stk.pop();
            idx++;
        }
    }

    rep(i, 0, N) if (P[i] != A[i]) {
        printf(":(\n");
        return;
    }

    printf("%s\n", ans.c_str());
}