UnKoder #08 : B. Unique Brackets

Bracket系の問題はCFに多いイメージ。
https://www.hackerrank.com/contests/unkoder-08/challenges/unique-brackets

問題

'('、')'、'?'で構成される文字列Sがある。
S中の'?'を'('か')'に置き換えた文字列をS'とする。

S'中の括弧が矛盾なく対応するようなS'が、2通り以上作れるか判定せよ。
なお、条件を満たすS'が1個は存在することが保証される。

解法

まずS'を1通り作り、そこから他のS'が作れるか判定しよう。

S'の作り方は簡単で、全体で開きかっこの数が|S|の半分に達するまで、先頭から順に'?'を'('にしていけば良い。
また、その際各位置での閉じてない開きかっこの数を計算しておく。

こうして作ったS'において、'?'から変換して生成された'('・')'の対を1つ選択し、それぞれ向きを逆にしても全体が矛盾しない(閉じてない開きかっこがマイナスにならない)なら、その対の向きを逆にできる＝S'が複数生成できるとなる。
'('と')'の対は全パターン試す必要はなく、最寄りのペアだけ試せば十分である。

string S,S2;
int L;
int FO;
int h[101000], nex[101000];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	S2=S;
	L=S.size();
	FO=L/2;
	
	FOR(i,L) if(S[i]=='(') FO--;
	MINUS(nex);
	
	x=0,y=-1;
	FOR(i,L) {
		if(S[i]=='(') h[i]=h[i-1]+1;
		else if(S[i]==')') h[i]=h[i-1]-1;
		else {
			if(y>=0) nex[y]=i;
			y=i;
			if(FO) S2[i]='(', h[i]=h[i-1]+1, FO--;
			else S2[i]=')', h[i]=h[i-1]-1;
		}
	}
	
	FOR(i,L) if(S2[i]=='(' && nex[i]>=0 && S2[nex[i]]==')') {
		if(count(h+i,h+nex[i],1)==0) return _P("No\n");
	}
	cout<<"Yes"<<endl;
}

まとめ

幸い1発ACが取れました。