SRM 519 Div 1 - Problem 250 BinaryCards

問題
SRM 519 Div 1 - Problem 250 BinaryCards
TopCoder Statistics - Problem Statement

使用言語
C++

問題概要
0から63までの数字のカード(全て1枚ずつ)を使う．数字xのカードには2ˆxのドットが描かれている．
最初全てのカードは伏せられている．AからBまでの連続する整数について，カードを表にして，カードに描かれるドットの数で表す．表になったカードのドットの合計を求める．

方針
表のカード(のドットの数)について考えると，
　6: 2 4
　7: 1 2 4
　8: 8
となる．表になったドットは 1+2+4+8=15
→各数字のビット和でわかりそう

しかし，O(N)で最大10ˆ18になるので連続する整数のビット和を全て取るのは現実的でない．

ここで単純化して考える．
A = 2ˆ30 + 1, B = 2ˆ30 + 24とする．
答え(Cとする)にはもちろんA, Bが含まれる(C|A==A, C|B==B)
差分について考えると，23 = 16 + 4 + 2 + 1 = 0x10111
これの最上位ビット以下のは全て1になりそう（例 20ˆ3+8）
なのでそれ以下を1にする．

所感
・わかりにくすぎる問題文に反して，楽しい問題
・コード短すぎ問題

コード

class BinaryCards {
    public:
    long long largestNumber(long long A, long long B) {
      ll ans = A | B;
      //差分の最上位ビット以下のビットが1になるようにOR
      //どうせ最上位以下のビットは全て1になるので，最上位1つずつ左シフトしてforループ
      for (ll i = B - A; i > 0; i = i>>1) ans |= i;
      return ans;
    }
};