ABC064: D - Insertion

問題

D - Insertion

解説

括弧列がvalidかどうかの問題は、括弧の対応を +1, -1 に対応させて数え上げて解くことが定石。

この系統の最も一般的な問題は、文字列長を最小にするだけの問題である。( -> +1, ) -> -1 と対応させた場合、左から累積して値が負になるときに(を付け足しながら +1 させ、最後に累積値の数だけ ) を末尾に加えれば良い。しかし本問題は、文字列長が最小であるうち、辞書順最小の文字列を求める必要があるため、これではうまくいかない。

これを解決するためには、適宜対応する括弧を挿入することはせずに、末尾に累積値分の括弧を加える操作のみを行い、その操作を左右からそれぞれ行えば良い。

つまり、まず文字列Sに対して、(の数が過剰な状態は、最も右に)を過剰である分だけ付け足すことで解消する。 次に、同じように)の数が過剰な状態は、最も左に(を過剰である分だけ付け足すことで解消すればよい。

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";
}