C - Move Brackets

cpcodeforcesdiv3greedystringbracket string

最終更新日

問題

https://codeforces.com/contest/1374/problem/C (新しいタブで開く)

問題文

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

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

制約

サンプル

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