Serval and Parenthesis Sequence [Codeforces Round #551 (Div. 2) C]

https://codeforces.com/contest/1153/problem/C

長さNの不完全かもしれないカッコ列がある。
?を適切に(か)に変えて、以下の条件を満たすものを構築せよ。
構築できないなら:(を出力。

• 全体が正しいカッコ列
• 全体以外の全ての接頭文字列が正しいカッコ列でない

S

≦3*10^5

解説

https://codeforces.com/contest/1153/problem/C

頭から貪欲に構築していこう。
?はなるべく(にしたほうが、途中で正しいカッコ列が作られにくいので、なるべく(にするように構築する。
後々の調整で正しいカッコ列にできない場合のみ)を入れていく。
　
実装としては最初に(の数up, )の数down、?の数noneを数えておき、後々の調整で使用していく。
先頭が)となっていたら、自分の実装ではバグったので、最初に)なら弾くようにしてある。

int N; string S;
//---------------------------------------------------------------------------------------------------
#define ng ":("
string solve() {
	if (S[0] == ')') return ng;

	int up = 0, down = 0, none = 0;
	rep(i, 0, N) {
		if (S[i] == '(') up++;
		else if (S[i] == ')') down++;
		else none++;
	}

	int cur = 0;
	rep(i, 0, N) {
		if (S[i] == '(') up--, cur++;
		else if (S[i] == ')') down--, cur--;
		else {
			none--;

			// '('
			if (cur + 1 + up - down <= none) cur++, S[i] = '(';
			else cur--, S[i] = ')';
		}
		
		if (cur == 0) {
			if (i == N - 1) return S;
			return ng;
		}
	}

	return ng;
}
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N >> S;
	cout << solve() << endl;
}