ABC117 D. XXOR

問題

N個の非負整数A_iと、非負整数Kが与えられる。
ここで、f(X) = Σ (X xor A_i) (0 <= X <= K)という関数fを定義する。
この関数fの最大値を求めよ。

制約

• 1 <= N <= 10^5
• 0 <= K <= 10^12
• 0 <= A_i <= 10^12

解法

関数fはビットごとに0にするか1にするかで関数の値を独立に求められるので、雰囲気、上から貪欲に求められそうに見える。
しかしこれは普通に嘘で、貪欲が適用できる場合というのは「選択しなかった場合の最終スコアが、選択した場合の最終スコアを超えない」こと(それを証明できること)が必要。
(今回の場合、Nが大きいケースなどで、下位ビットの方で大きい値が加算される可能性がある)

なので、ちゃんと(全)探索を考える。

今、i bit目を考えているとする。
i bit目を0にするか1にするかが選べるが、Kを超えてはいけないので、「そこまで決めたビットの値+(1< K」ならば必ず0にしなければならない。そして、次のbitを同様に探索すればよい。

逆に0でも1でも選べる場合、0にしたらそれ以降のビットはどう選んでもKを超えないので、下位のすべてのbitでスコアが高くなる方のビットを貪欲に選んでよい。
1にした場合は、次のbitを同様に探索すればよい。

実装は、

• どこのビットを処理しているか: i
• そこまで決めたビットの値: X'
• そこまで決めたビットの分だけの関数のスコア: F'

を持ちながら再帰すればよい。