Codeforces #169 Div2 D "Little Girl and Maximum XOR"
問題
AからBの間でXORしたときに最大になるような
2つの整数を選び、そのXORしたときの値を返せ。
例)
A=1 B=2
2(10) xor 1(01) = 3(11)が最大
A=8 B=16
15(01111) xor 16(10000) = 31(11111)が最大
A=1 B=1
1(1) xor 1(1) = 0(0)が最大
制約
1 <= A <= B <= 10^18
考えた事(2時間)
AとBの数が大きく、最大で60ビットぐらいになっちゃうから、
ビット毎に全探索はむりだな~
答えとなる2つの数をx,y(x<=y)として、yは1、xは0にしても大丈夫な
最上位のビットを探す。
たとえばA=8 B=16ならば重み16のビット
A=100 B=50ならば重み64のビット
A=5 B=3ならば重み4のビット
A=16 B=17ならば重み1のビット
・・・がそんなビットになる。
そのビットはyは1、xは0にしなきゃだめ。
(そうしなきゃxorしたとき最大値にならない)
そしてyはそれより下位のビットを全部0に
xはそれより下位のビットを全部1にした時、xorで最大値となる。
y=..1000000..
x=..0111111..
だから見つけたビットから全部1にした1111111・・・という値が答え
ソースコード
typedef long long ll; int main() { ll A, B; cin >> A >> B; // yは1に、xは0にすることが出来る // 最上位のビットを見つける int b = 62; for( ; b >= 0; b-- ){ ll num = 1LL << b; if( A < num && num <= B ){ // あった! break; }else if( num <= A && num <= B ){ // このビットは両方1にしなくちゃだめ A -= num; B -= num; }else{ // このビットは両方0にしなくちゃだめ } } ll res = 0; for( ; b >= 0; b-- ){ ll num = 1LL << b; res += num; } cout << res << endl; }