MUJINプログラミングチャレンジ : D - 括弧列 / Parenthesis Sequence

これは解けて良かった。
http://mujin-pc-2016.contest.atcoder.jp/tasks/mujin_pc_2016_d

問題

'('')''?'で構成されたN文字の文字列Sが与えられる。
これに対し、２値(L[i],R[i])で構成されるクエリが与えられる。

各クエリに対し、部分文字列S[L[i]...R[i]]に対し、'?'を適切に'('')'に置換した場合、この部分文字列が正当な括弧列(よくある括弧の対応付けが正常な文字列。詳細は省略)であるかどうかを判定せよ。

解法

事前にSの各prefixにおける'('')''?'の登場回数を数え上げておこう。
各クエリに対し、S[L[i]...R[i]]内で開き括弧と閉じ括弧の数は等しくなければいけないので、'?'のうちいくつ開き括弧にすれば条件を満たすかは計算で求められる。
また、括弧列の特徴としてできるだけ前に開き括弧が来た方が正当な括弧列になりやすい(途中閉じ括弧の方が多いという状態になりにくい)ということがわかる。

例えばS[L[i]..T]までは'?'を開き括弧、S[(T+1)..R[i]]の間は'?'を閉じ括弧にすると、両括弧の数が一致するとする。
その区間において、開き括弧の方が余剰である数がS[L[i]]とS[R[i]]の位置が最小であるかどうかを求めればよい。
それには、'?'を開き括弧とした場合のSにおける開き括弧余剰数のRange Minimum Queryと、'?'を閉じ括弧とした場合のSにおける開き括弧余剰数のRMQを求めればよい。

以下の問題では自分はRMQ相当を求めるのに定番のSegTreeではなくダブリングを用いてしまった。
とはいえ計算量は同等なので大した問題ではない。

int N;
string S;
int O[101010],C[101010],H[101010];
int Q;
pair<pair<int,int>,int> QQ[101010];

int ok[101010];
int pa[101010];

int dif[2][1001010][20];
int heko[2][1001010][20];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S;
	FOR(i,N) {
		O[i+1]=O[i]+(S[i]=='(');
		C[i+1]=C[i]+(S[i]==')');
		H[i+1]=H[i]+(S[i]=='?');
		if(S[i]=='(') dif[0][i+1][0]=dif[1][i+1][0]=1;
		if(S[i]==')') dif[0][i+1][0]=heko[0][i+1][0]=-1, dif[1][i+1][0]=heko[1][i+1][0]=-1;
		if(S[i]=='?') {
			dif[0][i+1][0]=1;
			dif[1][i+1][0]=heko[1][i+1][0]=-1;
		}
	}
	
	FOR(x,17) {
		FOR(i,N+2) {
			FOR(j,2) {
				dif[j][i][x+1]=dif[j][i][x]+dif[j][i+(1<<x)][x];
				heko[j][i][x+1]=min(heko[j][i][x],dif[j][i][x]+heko[j][i+(1<<x)][x]);
			}
		}
	}
	
	cin>>Q;
	FOR(i,Q) {
		int L,R;
		cin>>L>>R;
		
		if((R-L)%2==0) {
			_P("No\n");
			continue;
		}
		
		int dd=(O[R]-O[L-1])-(C[R]-C[L-1]);
		int fr=H[R]-H[L-1];
		
		if(abs(dd)>fr) {
			_P("No\n");
			continue;
		}
		
		int op=(fr-dd)/2;
		int cl=(fr+dd)/2;
		
		int T=L-1;
		for(x=17;x>=0;x--) if(T+(1<<x)<=R) {
			y=T+(1<<x);
			int dd=H[y]-H[L-1];
			if(dd<=op) T+=1<<x;
		}
		
		int d=0,h=0;
		for(x=17;x>=0;x--) {
			if(T+1>=L+(1<<x)) {
				h=min(h,d+heko[0][L][x]);
				d+=dif[0][L][x];
				L+=1<<x;
			}
		}
		for(x=17;x>=0;x--) {
			if(R+1>=L+(1<<x)) {
				h=min(h,d+heko[1][L][x]);
				d+=dif[1][L][x];
				L+=1<<x;
			}
		}
		if(h==0) _P("Yes\n");
		else _P("No\n");
		
	}
	
	
}

まとめ

括弧列に明にSegTreeによるRMQを使うという意識がなかった。
それでもなんとか解けて良かった。