yukicoder : No.1377 Half xor Half

この回は参加が遅れたのでここまで本番に到達せず。
https://yukicoder.me/problems/no/1377

問題

長さ2Nの01で構成された文字列S,Tが与えられる。2Nは偶数である。
Sに対し、以下の処理を行う。

• 整数xを選ぶ
• 0以上N未満の整数iに対し、S[(x+i) mod 2N] ^= S[(x+i+N) mod 2N] で値を更新する

2N回以下の処理でSをTにできるか、可能ならその手順を示せ。

解法

整数xを選んだあと、x+Nを選ぶと、S[x]とS[x+N]の2値にだけ変化をもたらすことができる。
そこで、2手で2値をTに合わせることを考える。

S[x]とS[x+N]の対が(0,0)の時、どう2手をとっても(0,0)にしかならない。
反対に、S[x]とS[x+N]の対が(0,0)以外の時、「何もしない」「xを先に選ぶ」「x+Nを先に選ぶ」のいずれかにより(0,0)以外のいずれにも遷移できる。
よって上記の遷移パターンを列挙しよう。

int N;
string S,T;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S>>T;
	vector<int> R;
	FOR(i,N) {
		x=(S[i]=='1')+(S[i+N]=='1')*2;
		y=(T[i]=='1')+(T[i+N]=='1')*2;
		if((x==0)!=(y==0)) return _P("-1\n");
		if(x==1&&y==2) R.push_back(i+N), R.push_back((i+N+1)%(2*N));
		if(x==1&&y==3) R.push_back(i), R.push_back(i+1);
		if(x==2&&y==1) R.push_back(i), R.push_back(i+1);
		if(x==2&&y==3) R.push_back(i+N), R.push_back((i+N+1)%(2*N));
		if(x==3&&y==1) R.push_back(i+N), R.push_back((i+N+1)%(2*N));
		if(x==3&&y==2) R.push_back(i), R.push_back(i+1);
	}
	
	
	cout<<R.size()<<endl;
	FORR(r,R) cout<<r<<endl;
}

まとめ

範囲を選択するタイプの処理、1ずらしは典型テクかな？