Codeforces #459 Div2 C Monster

• 問題

問題概要

文字列Sが与えられる.
'()', '((()))', '()(())'などの'('と')'が対応している文字列を有効な文字列とする.
')('はダメ. また,'?'はどちらにも変換できる.
l ,r (1<=l < r<=|S|)でS[l..r]が有効な文字列であるような組の数を求めよ.
1 <= |S| <= 5*10³

解法

全 1 <= l < r <= |S| について判定する.
'('を+1,')'を-1とする.
')'がその前の'('と'?'の数より多いと決して有効でなくなるため,それをcheck変数でチェックする.
cntに関してはできるだけ閉じる -> '?' を ')' にするように数えていくが,
')' を作りすぎてもいけないので cnt = -1となったら, 1に変換する.
これは ')' と変換した '?' を '(' にすることに相当する.
cnt = 0 となる時, 有効な文字列に変換できる.
全パターンがO(|S|^2),各O(1)なので十分間に合う.

メモ

解けなかったので,うーん,って感じ.

コード

#include "bits/stdc++.h"

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i, x, n) for(int i = x; i >= n; i--)
#define rrep(i, n) RREP(i,n,0)
#define pb push_back

using namespace std;

using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,int>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60, lmod = 1e9+7;

int main(){
  string s; int N;
  cin >> s; N = s.size();
  int ans = 0;
  rep(i,N-1){
    int check = 0, cnt = 0;
    REP(j,i,N){
      if(s[j]=='(') check++,cnt++;
      else if(s[j]==')') check--,cnt--;
      else check++,cnt--;
      if(check<0) break;
      if(cnt<0) cnt += 2;
      // cout << i << "," << j << " = "<< check << "," << cnt << endl;
      if(cnt==0) ans++;
    }
  }
  cout << ans << endl;
  return 0;
}