Codeforces #712 Div1 : A. Balance the Bits

4完の割に順位が低いな。
https://codeforces.com/contest/1503/problem/A

問題

N要素の0/1列Sが与えられる。
今ここで、N文字の2つの括弧列A,Bを作りたい。
その際、S[i]=1ならA[i]=B[i]、S[i]=0ならA[i]!=B[i]でなければならない。

Sに対し、A,Bがともに正しい括弧列となるようなものが可能なら1つ構築せよ。

解法

S[i]=1となるiについては、前半半分はA[i]=B[i]='('、後半半分はA[i]=B[i]=')'としよう。
また、S[i]=0となるiについてはA[i]とB[i]が交互に開きカッコになるようにする。

あとは、こうして構築した文字列A,Bが正しい括弧列か✓すればよい。

int T,N;
string S;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>S;
		
		string R[2];
		int cur=0,step=0;
		int num[2]={};
		FOR(i,N) num[S[i]-'0']++;
		FOR(i,N) {
			if(S[i]=='1') {
				if(cur<num[1]/2) {
					R[0]+='(';
					R[1]+='(';
				}
				else {
					R[0]+=')';
					R[1]+=')';
				}
				cur++;
			}
			else {
				R[step]+='(';
				R[step^1]+=')';
				step^=1;
			}
		}
		FOR(i,2) {
			int cur=0;
			FOR(j,N) {
				if(R[i][j]=='(') cur++;
				if(R[i][j]==')') cur--;
				if(cur<0) break;
			}
			if(cur!=0) break;
		}
		if(i==2) {
			cout<<"YES"<<endl;
			cout<<R[0]<<endl;
			cout<<R[1]<<endl;
		}
		else {
			cout<<"NO"<<endl;
		}
		
	}
}

まとめ

A問題の割にコード量多め。考察は簡単だけどね。