Codeforces #459 Div2C

Codeforces #459 Div2C TheMonster

(または)または?からなる文字列sが与えられる.sの部分文字列のうち,?を(または)に置きかえたとき正しいカッコ列(左カッコと右カッコの対応がとれた列)に出来るものはいくつあるか?という問題.

始点を固定して,そこから伸ばしていく.カッコ列といえばA=(左カッコの数)-(右カッコの数)が常に0以上(★)であって末尾まで見たときAが0になっていればいいという有名な話がある.今回は?があるのだが,それは問題が生じるまで全て)だとみなしてしまう.ある所でAが負になったら,そこでこれまでに出てきた?を)から(にかえて+2してやる(もう?がのこっていなければ無理).この方法で文字列を作っていくと,★を満たす中で最も(がすくないものが見つかる.このときA=0ならばOK.

ソースコード

#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
int main() {
    string s;
    cin >> s;
    int n = s.size();
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int now = 0;
        int cnt = 0;
        for (int j = i; j < n; j++) {
            if (s[j] == '(') now++;
            else now--;
            if (s[j] == '?') cnt++;
            if (now < 0) {
                if (cnt == 0) break;
                cnt--;
                now += 2;
            }
            else if (now == 0) {
                ans++;
            }
        }
    }
    cout << ans << endl;
}