Codeforces #262 Div2 D. Little Victor and Set

なかなか面白いconstruction問題。
http://codeforces.com/contest/460/problem/D

問題

整数L,R,Kが与えられる。
L～Rの整数のうち、1個～K個の範囲の整数を含む整数の集合Sのうち、全要素のxorが最小のものを答えよ。

解法

幾つか場合分けする。

• K==1の場合、Sの唯一の要素が全要素のxorになるので、当然S={L}が答え。
• L+1==RかつK==2の場合、L・R・L^Rのいずれか最小値を答える。
• ここまでの時点で、K>=2かつL+1
  • R-L>=10なら全要素総当たりで0を探す。
  • K>=4なら、2m ^ (2m+1) ^ (2m+2) ^ (2m+3)==0なので0を作れることが確定する。
  • K==3において、LのMSB以外をXXXXXXと表現すると、Lは1XXXXXXとおける。この時、下記のように10XXXXXXと11000000をもう２要素選べばxorを0に出来る。よって11000000<=Rなら0を作成できる。

  1XXXXXX
^10XXXXXX
^11000000
---------
=00000000

ll L,R,K;

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>L>>R>>K;
	if(K==1) return _P("%lld\n1\n%lld\n",L,L);
	if(R-L==1) {
		if((L^R) < L) return _P("%lld\n2\n%lld %lld\n",L^R,L,L+1);
		return _P("%lld\n1\n%lld\n",L,L);
	}
	
	if(R-L<=10) {
		int mask;
		FOR(mask,1<<(R-L+1)) if(mask) {
			ll tot=0;
			FOR(i,R-L+1) if(mask&(1<<i)) tot^=L+i;
			if(tot==0 && __builtin_popcount(mask)<=K) {
				_P("0\n%d\n",__builtin_popcount(mask));
				FOR(i,R-L+1) if(mask&(1<<i)) _P("%lld ",L+i);
				return;
			}
		}
	}
	
	if(K>=3) {
		int lb=0;
		while(1LL<<(lb+1) <= L) lb++;
		ll aa=(1LL<<(1+lb))+(L-(1LL<<lb));
		ll bb=(1LL<<(1+lb))+(1LL<<lb);
		if(bb<=R) return _P("%lld\n3\n%lld %lld %lld\n",0LL,L,aa,bb);
	}
	L=(L+1)/2*2;
	if(L+3<R && K>=4) return _P("0\n4\n%lld %lld %lld %lld\n",L,L+1,L+2,L+3);
	_P("1\n2\n%lld %lld\n",L,L+1);
}

まとめ

幾つか場合分けがあるけど、なかなかバリエーションに富んでいて面白いね。