yukicoder : No.862 XORでX

汚い分岐を書いてしまった。
https://yukicoder.me/problems/no/862

問題

正整数N,Xが与えられる。
100005以下の異なる整数をN個選び、xorを取った値がXとなるようにせよ。

解法

Editorialは綺麗だが、自分はだいぶ汚いやり方をしてしまった。
以下の事実を利用する。

• 4k, 4k+1, 4k+2, 4k+3と4連続する数のxorは0である
• k=0の場合、1,2,3と3連続する数のxorは0である

これらを利用し、X周辺じゃない数値を4つずつ使ってNを減らしていこう。
そのため、以下はN%4の値で大きく分岐し、あとはX≦3の時だけ注意している。

int N,X;
vector<int> V;

void hoge() {
	int i;
	for(i=4;i<=100000;i+=4) if(N) {
		if(X<i || i+4<=X) {
			V.push_back(i);
			V.push_back(i+1);
			V.push_back(i+2);
			V.push_back(i+3);
			N--;
		}
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>X;
	if(N%4==0) {
		N/=4;
		if(X>=4) {
			V.push_back(1);
			V.push_back(2);
			V.push_back(3);
			V.push_back(X);
			N--;
			hoge();
		}
		else {
			N--;
			hoge();
			if(X==1) {
				V.push_back(100000);
				V.push_back(100002);
				V.push_back(1);
				V.push_back(2);
			}
			if(X==2) {
				V.push_back(100000);
				V.push_back(100001);
				V.push_back(1);
				V.push_back(2);
			}
			if(X==3) {
				V.push_back(100000);
				V.push_back(100001);
				V.push_back(1);
				V.push_back(3);
			}
		}
	}
	else if(N%4==1) {
		N--;
		V.push_back(X);
		N/=4;
		hoge();
	}
	else if(N%4==2) {
		N/=4;
		hoge();
		if(X==1) {
			V.push_back(2);
			V.push_back(3);
		}
		else if(X==2) {
			V.push_back(1);
			V.push_back(3);
		}
		else if(X==3) {
			V.push_back(1);
			V.push_back(2);
		}
		else {
			V.push_back(X^1);
			V.push_back(1);
		}
	}
	else if(N%4==3) {
		if(X>=4) {
			N/=4;
			hoge();
			for(i=4;i<=100000;i+=4) {
				if(X>=i&&X<i+4) {
					if(i!=X) V.push_back(i);
					if(i+1!=X) V.push_back(i+1);
					if(i+2!=X) V.push_back(i+2);
					if(i+3!=X) V.push_back(i+3);
				}
			}
			
		}
		else {
			N/=4;
			hoge();
			if(X==1) {
				V.push_back(100000);
				V.push_back(100002);
				V.push_back(3);
			}
			if(X==2) {
				V.push_back(100000);
				V.push_back(100001);
				V.push_back(3);
			}
			if(X==3) {
				V.push_back(100000);
				V.push_back(100001);
				V.push_back(2);
			}
		}
	}
	sort(ALL(V));
	FORR(x,V) cout<<x<<endl;
	
}

まとめ

シンプルなアイデアだけにどこかで出題されてそうな印象。