考察
最大値の最小化は最上位bitから辞書順に決まり、xのbit bは全a_iのbitを同時に反転する。
現在候補集合のbit bが一様ならx_bを合わせて出力bitを全て0にできるが、0/1両方なら最大値のbit bは必ず1になる。
採用する候補: bitを上位から再帰し、混在時はx_b=0/1の二案で高bit1となる片側groupだけを残して小さい再帰値を選ぶ。
棄却する候補: xを0≤x<2^30で全列挙してmax_i(a_i xor x)を取る。
x候補が約10^9個あり不可能である。
solve(V,b)を定義する。b<0なら0、一方groupだけならそのgroupでsolve(b-1)、両groupがあれば2^b+min(solve(V0,b-1),solve(V1,b-1))を返す。初期V=A,b=29の値が答え。
典型の発動条件
XORの上位bit divide-and-conquer
発動条件: 共通xとのXOR後のmin/maxを最適化し、値域が固定bit幅のとき。
現在bitで0/1にpartitionし、上位bitが決める支配関係から片側を落とす。
bit trie的再帰
発動条件: 整数集合をprefix bitごとのgroupへ分ける処理が必要なとき。
上位からpartitionした再帰tree上で各要素を一度ずつ下ろす。
問題固有の要素
混在bitでは最大側となるinput groupがx_bによって入れ替わり、二案の下位最適値のminを取るrecurrenceになる。
別の問題へ持ち帰る視点: global XOR最適化では、xの1bit選択がどのgroupをextremum候補にするかを上位bit優先で追う。
正当性
bit bが混在するとanswerへ2^bが確定し、x_b=0ならinput bit1 group、x_b=1ならbit0 groupだけが最大候補として下位bit比較に残る。 捨てたgroupは出力bit bが0なので、下位bitが何であっても高bit1のgroupを越えず、以後考慮不要である。 各要素はbit trieの1経路に沿って処理され、未知xを全列挙せず最上位差で候補を分割できる。
実装上の注意
- 一様bitでも対応するx_bを自由に選んで0化できるためanswerへ2^bを足さない。
- vector copyを各再帰で過剰に行わず、sort済み区間やbucket moveで総要素処理量を抑える。
復習の核
- bit bで混在する小集合についてx_b=0/1後の最大候補groupを色分けし、なぜもう片側を完全に捨てられるか説明する。
計算量と制約
時間
O(NB)、B=30。区間またはbucketによるbit分割。
空間
O(N+B)、入力再配置と再帰stack。
制約との対応
公式制約の確認範囲: Time limit: 2.5 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 1.5 \times 10^5; 0 \leq a_i \lt 2^{30}; All values in the input are integers.
出典