kmjp's blog

競技プログラミング参加記です

Codeforces #169 Div2. D. Little Girl and Maximum XOR

さてD。点数の割には意外と簡単?
http://codeforces.com/contest/276/problem/D

問題

2つの整数値L,Rが与えられる。
LとRの間の数値A,Bを選択したとき、A xor Bの最大値を答える。

解法

LとRの最上位ビットの位置が同じ場合、A,Bは常にそのビットを持つので、A ^ Bにもそのビットは立たない。
よってLとR両方そのビットを落とす。

上記処理を加えると、(L==Rの時)LとRが両方0になるか、もしくはLとRの最上位ビットの位置が異なるようになる。
前者はA=B=0しか取れないので最大値は0。
後者は、L=0XXXXX、R=1YYYYYのようなビット構成の場合、A=011111、B=100000を取れば最大値111111が取れる。

ll L,R;

void solve() {
	int f,r,i,j,k,l,x,y;
	ll re = 0;
	
	cin >> L >> R;
	while(L>0 && R>0) {
		ll lt=1;
		ll rt=1;
		while(lt*2<=L) lt<<=1;
		while(rt*2<=R) rt<<=1;
		if(lt!=rt) break;
		L ^= lt;
		R ^= rt;
	}
	
	if(R==0) _P("0\n");
	else {
		ll rt=1;
		while(rt*2<=R) rt<<=1;
		cout << (rt*2-1) << endl;
	}
	
	return;
}

まとめ

ビット処理がちょっとまどろっこしくなってしまった。
もっときれいに書けないかな。

以前のSRMでもxorしてく問題があったので、おかげで割と簡単に気づけた。
TopCoder SRM 564 Div1 Hard DefectiveAddition - kmjp's blog