CodeTON Round 7 : F. Bracket Xoring

意外とコードは短い。
https://codeforces.com/contest/1896/problem/F

問題

長さ2Nの01で構成される数列Sが与えられる。
以下の処理を最大10回行い、Sをすべて0にせよ。

2N文字の正しい括弧列Bを指定する。
i文字目にある開き括弧とj文字目にある閉じ括弧が対応する場合、S[i,j]を01反転する。

解法

01が反転する条件は、

• iが奇数でかつB[i]が開き括弧の時
• iが偶数でかつB[i]が閉じ括弧の時

である。

()()....() という文字列と、 *1 という文字列について、適宜")("となっている箇所を"()"と置き換えても正しい括弧列であることは変わらない。
これを利用して、うまく1を消していこう。

int T,N;
string S;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>S;
		vector<string> V;
		FORR(c,S) c-='0';
		if(S[0]!=S.back()||count(ALL(S),1)%2) {
			cout<<-1<<endl;
			continue;
		}
		
		if(S[0]==1) {
			s="";
			FOR(i,N) s+="()";
			V.push_back(s);
			FORR(c,S) c^=1;
		}
		s="(";
		FOR(i,N-1) s+="()";
		s+=")";
		S[0]^=1;
		S.back()=1;
		for(i=2;i<2*N-1;i+=2) {
			if(S[i]!=S[i-1]) {
				swap(s[i],s[i+1]);
				S[i]^=1;
				S[i+1]^=1;
			}
		}
		V.push_back(s);
		/*
		FORR(c,S) cout<<(char)('0'+c);
		cout<<" ";
		*/
		s="";
		FOR(i,N) s+="()";
		FORR(c,S) c^=1;
		for(i=1;i<2*N-2;i+=2) {
			if(S[i]!=S[i-1]) {
				swap(s[i],s[i+1]);
				S[i]^=1;
				S[i+1]^=1;
			}
		}
		V.push_back(s);
		/*
		FORR(c,S) cout<<(char)('0'+c);
		cout<<endl;
		*/
		
		cout<<V.size()<<endl;
		FORR(v,V) cout<<v<<endl;
	}
}

まとめ

色々解法ありそう。

*1:)()()()....(