ABC064: D - Insertion
問題
解説
括弧列がvalidかどうかの問題は、括弧の対応を +1, -1 に対応させて数え上げて解くことが定石。
この系統の最も一般的な問題は、文字列長を最小にするだけの問題である。(
-> +1, )
-> -1 と対応させた場合、左から累積して値が負になるときに(
を付け足しながら +1 させ、最後に累積値の数だけ )
を末尾に加えれば良い。しかし本問題は、文字列長が最小であるうち、辞書順最小の文字列を求める必要があるため、これではうまくいかない。
これを解決するためには、適宜対応する括弧を挿入することはせずに、末尾に累積値分の括弧を加える操作のみを行い、その操作を左右からそれぞれ行えば良い。
つまり、まず文字列に対して、(
の数が過剰な状態は、最も右に)
を過剰である分だけ付け足すことで解消する。
次に、同じように)
の数が過剰な状態は、最も左に(
を過剰である分だけ付け足すことで解消すればよい。
int main() { int N; cin >> N; string S; cin >> S; { int count = 0; rep(i, N) { if (S[i] == '(') count++; if (S[i] == ')') count--; if (count < 0) count = 0; } rep(i, count) { S += ')'; } } N = S.size(); { int count = 0; for(int i = N - 1; i >= 0; i--) { if (S[i] == ')') count++; if (S[i] == '(') count--; assert(count >= 0); } rep(i, count) { S = "(" + S; } } cout << S << "\n"; }