CF Round #653 C - Move Brackets

問題

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

問題文

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

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

制約

• $1 \le t \le 2000$
• $2 \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;
}