問題
$N$ 個の非負整数 $a_1, \dots, a_N$ が与えられる。異なる添字 $i \ne j$ を選んだときの $a_i \oplus a_j$（XOR）の最大値を求めよ。
制約
| パラメータ | 範囲 | 備考 |
|---|---|---|
| $N$ | $2 \le N \le 2\times10^5$ | 要素数 |
| $a_i$ | $0 \le a_i < 2^{30}$ | 非負整数 |
入出力例
入力例1
4
3 10 5 25出力例1
28$5 \oplus 25 = 28$（$5=00101_2$, $25=11001_2$, XOR$=11100_2=28$）が最大。
概念図
ヒント
ヒント1（方向性）
全ペア $O(N^2)$ では間に合わない。上位ビットからできるだけ多くのビットを「1にできる」組み合わせを選びたい。
ヒント2（アプローチ）
全数を固定長 $B$ bit のビット列としてトライ木に挿入する。各数 $x$ について上位ビットから「$x$の現在のビットと逆のビット」を持つ子があればそちらへ進む。
ヒント3（ほぼ答え）
def query_max_xor(x):
node = 0; result = 0
for b in range(BIT-1, -1, -1):
bit = (x >> b) & 1
want = 1 - bit
if children[node][want] != -1:
result |= (1 << b); node = children[node][want]
else:
node = children[node][bit]
return result模範解答
import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
a = list(map(int, data[1:1 + n]))
BIT = 30
children = [[-1, -1]]
def insert(x):
node = 0
for b in range(BIT - 1, -1, -1):
bit = (x >> b) & 1
if children[node][bit] == -1:
children.append([-1, -1])
children[node][bit] = len(children) - 1
node = children[node][bit]
def query_max_xor(x):
node = 0
result = 0
for b in range(BIT - 1, -1, -1):
bit = (x >> b) & 1
want = 1 - bit
if children[node][want] != -1:
result |= (1 << b)
node = children[node][want]
else:
node = children[node][bit]
return result
for x in a:
insert(x)
ans = 0
for x in a:
ans = max(ans, query_max_xor(x))
print(ans)
main()計算量: 挿入・クエリともに $O(\text{BIT})$、全体 $O(N\log(\max a))$。
Step-by-Step 解説
Step 1: ビット幅の固定
$a_i < 2^{30}$ なのでBIT=30に固定し、リーディングゼロのズレを防ぐ。
Step 2: 全要素をトライに挿入
insert(x)は各ビットごとに子ノードを辿り、無ければ新規作成する。
Step 3: 各要素についてXOR最大の相手を貪欲に探索
上位ビットから「逆ビットを持つ子」を優先的に選ぶ。存在しなければ同じビット側へ進む。
Step 4: 全要素で最大値を更新
$N\ge2$保証のため答えは必ず他要素との組で決まる。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| ビット幅を可変にする | 要素ごとに桁数が揃わずXORがずれる | 制約から決まる固定幅（30bit）で統一 |
| 逆ビットの子がなければ諦める | 貪欲の本質を誤解 | 同じビット側へ進んで探索継続 |
| トライをdictで実装し低速化 | 実装の手軽さを優先 | 固定長配列でO(1)アクセス |
| N=1で自己XOR=0を採用 | 制約確認不足 | 本問はN≥2保証、一般化時は要注意 |
次のステップ
- 発展: 永続01-Trieによる「区間 $[l,r]$ 内での最大XORペア」クエリ
- 発展: XOR線形基底（Basis）との比較
- 次回予告: Kadane's Algorithm拡張（円環配列の最大部分和）
自己評価
理解度: / /
自分の回答:
気づき・メモ: