CF Round #653 C - Move Brackets


Tags:cpcodeforcesdiv3greedystringbracket_string

問題

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

問題文

長さ nn (偶数) の文字列 ss が与えられる。ss() のみからなる。ss の中に含まれる ( の数と ) の数は同じ。

1 回の操作で、任意の 1 つの index ii について、その文字を先頭か末尾に移動する。
正しい括弧列にさせるための最小の操作回数は?

制約

  • 1t20001 \le t \le 2000
  • 2n502 \le n \le 50

サンプル

4
2
)(
4
()()
8
())()()(
10
)))((((())
1
0
1
3

考察

( なら +1 、 ) なら -1 の累積和 (典型)
このとき、この累積和の最小値が答え。

前から順番に見ていくとき、この累積和がマイナスになったら、その ) を末尾に移動させることで、その時点までの和を +1 できるとみなせる (と思う)

コード

https://codeforces.com/contest/1374/submission/126805762

void solve() {
  int n;
  cin >> n;
  string s;
  cin >> s;
  int dep = 0;
  int ans = 0;
  rep(i, n) {
    if (s[i] == '(') {
      dep++;
    }
    else {
      dep--;
    }
    if (dep < 0) {
      ans = min(ans, dep);
    }
  }
  cout << -ans << endl;
}