Tenka1 Programmer Contest (2017) D - IntegerotS

問題
 提出コード
(こちらは手直しを加えたコードになります、最初に通したコードはこちらです)
手直しを加えた理由が、当初 $2^{30}$ がなぜかlong long型に収まらないと勘違いしていたため、unsigned long long型で計算をしているため、いろいろ複雑になってしまっているためです。それ以外にも、さらに考察を詰めて簡潔にしています。

解法

$K$ を2進数に直した時の、最上位の桁から順番に見ていきます。
$K=110111$ として考えてみます。
まずは、論理和が $K$ となるように整数を購入してみます。これが答えの候補の1つになります。最上位以外のビットが立っていない部分が存在しても問題ありません(例えば $K=110111$ の例の場合、 $110101$ となるようなパターンです)。これは、 $A_i$ と $K$ のORをとったときに $K$ と一致するような $i$ についての $B_i$ の総和になります。
続いて、他の答えの候補を探します。ありうるパターンとして、最上位のビットを使用するかどうか、という2つのパターンが存在します。それぞれのパターンでの最大値を求め、最初のものと合わせて一番大きいものが答えになります。

最上位のビットを使用しないパターン
このパターンでは、最上位ビットを使用していない $A_i$ はすべて買うことができます。
右から $t$ 桁目が最上位ビットだとすると、そのビットが表す数字は $2^{t-1}$ になります。
このとき、論理和が $2^{t-1}-1$ となるように購入することができます。これは、最上位ビット以外がすべて立っている状態を表しています。 $K=110111$ の例だと、 $011111$ になるようなパターンです。また、最上位ビット以外が立っていない部分が存在しても(例えば $011011$ )、必ず $K$ を下回っているため、とにかく最上位ビットが立っていない整数を全て買ってしまうのが一番価値が高くなります。これは、 $A_i\lt 2^{t-1}$ を満たす $B_i$ の総和になります。
最上位のビットを使用するパターン
最上位のビットを使用すると考えたとき、全ての $A_i$ について、最上位ビットは0であろうが1であろうが関係がなくなります。これらが購入することができるかどうかは、最上位ビット以外の決め方が関係します。
ということで、
$K$ および $A_i$ について、最上位ビットを無視した場合の最大値が答えになります。
$K$ をあたらしく $K-2^{t-1}$ と定義しなおせば、規模を縮小した問題に帰着できます( $A_i$ についても、 $2^{t-1}$ の減算をし忘れないようにします。 $A_i \geqq2^{t-1}$ を満たすものについてのみ行います)。