Codeforces #173 Div2. C. XOR and OR

さてここからが本番。
http://codeforces.com/contest/282/problem/C

問題

２進数(0で始まる場合もある)が変換元・変換先と２つ与えられる。
変換元の数値に対し、隣接する２桁に対し、片方をそのxor、もう片方をorで置き換えるという処理を実行できる。

上記処理を繰り返し、変換元を変換先に変換可能かどうかを答える。

解法

まず、処理を１回行うとどのように変化するかを調べてみる。

• 1と1 : 0(1^1)と1(1|1)
• 1と0 : 1(1^0)と1(1|0)
• 0と0 : 0(0^0)と0(0|0)

このことから以下のことがわかる。

• 0だけでは1を生成できない
• 1を減らすことはできるが、0個にすることはできない
• 1と0→1と1→0と1の様に位置を入れ替え可能なため、(隣接に限らず)任意の２桁の要素を入れ替えることができる

上記事実より、以下の様に処理可能。

• 変換元・先の桁数が異なるなら変換不可
• 変換元または変換先のいずれか片方がすべて0なら、変換不可
• それ以外は変換可

char str[1000001];
char str2[1000001];
int N[2][2];
int L;

int solve2(){
	int f,r,i,j,k,l,x,y;
	ll t;
	
	GETs(str);
	GETs(str2);
	L=strlen(str);
	if(L!=strlen(str2)) return 0;
	if(L==1) return (str[i]==str2[i]);
	
	FOR(i,L) N[0][str[i]-'0']++;
	FOR(i,L) N[1][str2[i]-'0']++;
	
	if(N[0][0]==L || N[1][0]==L) return N[0][0]==N[1][0];
	return 1;
}

void solve() {
	_P("%s\n",solve2()?"YES":"NO");
	return;
}

まとめ

解いたときは隣接しない要素も変換可能と勘違いして解いたが、あとで考えて要素の入れ替えが可能なので隣接は関係ないことに気づいた。