yukicoder : No.1228 I hate XOR Matching

場合分けに手間取った。
https://yukicoder.me/problems/no/1228

問題

整数K,Xが与えられる。
Kは2^20未満の整数、Xは10^9以下の非負整数である。

以下の条件を満たすN要素の整数列Aを構築可能か、可能なら構築せよ。

• 1≦N≦40
• 各要素は0以上2^20未満
• A中に同じ値は2回までしか登場しない
• Aの空でない部分集合のうち、xorを取るとKとなるのはX通り。

解法

細かく場合分けする。

• X=0の時：Aを{K^1}としておけばよい。
• K=0の時:
  • Xが(2の累乗)-1の時解がある。仮にX=2^m-1と置く。
  • Aに2^0～2^9を登録したうえで、1～mを登録しよう。
  • 後半の1～mを取る取り方は2^m通りあるが、いずれにしても全体のxorを0とするには最初の2^0～2^9の取り方は一意に定まる。
  • 1～mを1個も取らないと全体が空集合になるので、この時xorがKとなるのは2^m-1通り。
• K＞0の時:
  • Xが2の累乗の時解がある。仮にX=2^mと置く。
  • Kのうち(K and 2^p)==2^pとなるpを取ろう、
  • Aに2^p及び(2^pを除いて)2^0～2^9を登録したうえで、2^9以下でpビット目を持たないm個の異なる整数を登録しよう。
  • 後半のm個の値の取り方は2^m通り。全体のxorをKとするには最初の2^0～2^9の取り方は一意に定まる。
  • 全体のxorがKとなるには2^pを含まないといけないので空集合になることはなく、選び方は2^m-1通り。

int K;
ll X;
int Z;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>K>>X;
	
	
	if(X==0) {
		cout<<"Yes"<<endl;
		cout<<1<<endl;
		cout<<(K^1)<<endl;
		return;
	}
	
	vector<int> V;
	if(K==0) {
		if(X&(X+1)) {
			cout<<"No"<<endl;
			return;
		}
		X++;
		while(X%2==0) X/=2, Z++;
		FOR(i,10) V.push_back(1<<i);
		for(i=1;i<=Z;i++) V.push_back(i);
	}
	else {
		if(X&(X-1)) {
			cout<<"No"<<endl;
			return;
		}
		x=1;
		while((K&x)==0) x<<=1;
		y=1;
		V.push_back(K);
		FOR(i,9) {
			if(x==y) y<<=1;
			V.push_back(y);
			y<<=1;
		}
		while(X%2==0) X/=2, Z++;
		y=1;
		for(i=1;i<=Z;i++) {
			while(x&y) y++;
			V.push_back(y);
			y++;
		}
		
	}
	cout<<"Yes"<<endl;
	cout<<V.size()<<endl;
	FORR(v,V) cout<<v<<" ";
	cout<<endl;
	return;
}

まとめ

各問題を「面白い問題です」とほめつつ、問題名でhateしていくスタイル…。