AtCoder ARC #203 : B - Swap If Equal Sum

気付いてしまえばあっさり。
https://atcoder.jp/contests/arc203/tasks/arc203_b

問題

N文字のバイナリ文字列A,Bが与えられる。
Aの共通部分を持たない連続部分文字列のうち、1の数が等しい2か所を取り、swapすることを繰り返す。
A=Bにできるか判定せよ。

解法

• sum(A)はこの手順で変わらないので、sum(A)!=sum(B)なら解なし。
• 初期状態A=Bなら当然可能。
• sim(A)≧2なら常に可能。"01"や"10"を右にある"1"をswapすれば、1をすべて先頭に集められる。この手順は可逆なので、AからもBからも1を先頭に集められるため。
• sum(A)=1の場合、連続する0と単一の0をswapできるので、A,Bともに1が両端以外にあれば0の数を調整可能。そうでない場合不可。

int T,N,A[202020],B[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		x=0;
		y=0;
		FOR(i,N) {
			cin>>A[i];
			x+=A[i];
			y+=A[i];
		}
		FOR(i,N) {
			cin>>B[i];
			x-=B[i];
		}
		if(x) {
			cout<<"No"<<endl;
			continue;
		}
		
		FOR(i,N) if(A[i]!=B[i]) break;
		
		if(i==N||y==0||y>=2) {
			cout<<"Yes"<<endl;
		}
		else if(A[0]==1||A[N-1]==1||B[0]==1||B[N-1]==1) {
			cout<<"No"<<endl;
		}
		else {
			cout<<"Yes"<<endl;
		}
	}
	
}

まとめ

こういう問題、コーナーケース見落としてないか怖いな。