The Monster [Codeforces Round #459 Div.1 A]

http://codeforces.com/contest/917/problem/A

(,),?からなる文字列Sがある。
以下を満たす(i,j)の組は何通りあるか。

• i＜j
• S[i]～S[j]の連続部分文字列を'?'をうまく変換することで有効な括弧列にできる

解法

http://codeforces.com/contest/917/submission/34676454

i,jで全探索をする。
判定をO(1)で行う必要があるが、これはiを固定してjを動かす時に今までを考慮して判定していけばできる。
cnt := '('の数-')'の数
qu := '?'の数
chk := '('の数から')'と'?'を使ってなるべく引いていったときの数
最後が分かりにくいので、chk以外で考えてみる。
jを動かしていくと、
S[j] == '('ならcnt++
S[j] == ')'ならcnt--
S[j] == '?'ならqu++
となる。
この場合に括弧列が作れなくなる場合は「cnt < 0かつcnt+qu < 0」の場合である（今思えば後半の条件だけでいい）
これはquを全て'('にしても対応しない')'が出来てしまうためである。
cntが0でない場合はquを調整することでcntを0にできればans++する。
abs(cnt)で0との差をとり、その分quで調整する。調整後に残りのquが偶数なら使い切って0にできるし、そうでないなら使いきれずに括弧列が作れなくなる。
　
これで良さそうだが、?(のような連続部分列を誤って正しく判定してしまう。
これの判定の為にchkを使う。
S[j] == '('ならchk++
S[j] == ')'ならchk--, chmax(chk, 0)
S[j] == '?'ならchk--, chmax(chk, 0)
のようにカウントしていくが、これはなるべく'('を消すように操作している計算になる。
chmax(chk,0)としているのは'('が無い時は消せない為である。
なるべく消していっても'('が余ってしまうなら、正しい括弧列になれないため、0

string S;
int N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S;
    N = S.length();

    int ans = 0;
    rep(i, 0, N) {
        int cnt = 0, qu = 0, chk = 0;
        rep(j, i, N) {
            if (S[j] == '(') cnt++, chk++;
            else if (S[j] == ')') cnt--, chk--, chmax(chk,0);
            else qu++, chk--, chmax(chk, 0);

            if (cnt < 0 and cnt + qu < 0) break;
            int d = qu - abs(cnt);
            if (0 <= d and d % 2 == 0 and chk <= 0) {
                //printf("%d %d\n", i, j);
                ans++;
            }
        }
    }
    cout << ans << endl;
}