TopCoder SRM 519 Div2 Hard BinaryCards

Div1 EasyとDiv2 Hardが同じという珍しい回。さすがにDiv2では900pt。
http://community.topcoder.com/stat?c=problem_statement&pm=11552

問題

0～63番までの64枚のカードがあり、それぞれi番目のカードの表には2^i個の点が書かれている。
64枚のカードのうち、表を向いたカードの点の総和を現在の状態だとする。

初期状態として状態Aから開始し、状態A+1,A+2,...B-1,Bまですべてを遷移させたい。
各遷移間ではカードを最小枚数めくることができる。その際めくる順番は任意である。

この時通過しうる、最大の状態を答えよ。

解法

当然ながら各カードは数字を二進数表記したときの各桁に対応する。
(2の累乗)-1から2の累乗に移るとき、たとえば31(11111b)から32(100000b)に移るときは先に最上位bitに対応するカードをめくることで最大値63(111111b)を取ることができる。

この事実から、以下を再帰的に行えばよい。

• AとBの最上位桁が異なるなら、Bの最上位桁以下のbitが全部立つので最上位桁*2-1
• AとBの最上位桁が同じなら、その最上位桁の数字と、A,Bからその値を引いたものに再帰的に処理を行ったものになる。

class BinaryCards {
	public:
	long long largestNumber(long long A, long long B) {
		ll ar=1,br=1;
		if(B==0) return 0;
		
		while(ar*2<=A) ar*=2;
		while(br*2<=B) br*=2;
		
		if(br!=ar) return br*2-1;
		return br+largestNumber(A-br,B-br);
	}
};

まとめ

さすがに簡単。