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()); }