問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

$N$ 個の非負整数 $A_1, \dots, A_N$ が与えられる. 次の値を求めよ.

$\displaystyle \min_{x \in \mathbb{N}} \max_{1 \leq i \leq N} \left(A_i \oplus x \right)$

ただし, $\mathbb{N}$ を非負整数全体の集合とする.

制約

$1 \leq N \leq 1.5 \times 10^5$
$0 \leq A_i \lt 2^{30}$

解法

非負整数列 $E=(E_1, \dots, E_M)$ に対するこの問題の答えを $\operatorname{calc}(E)$ と書くことにする.

$E_1, \dots, E_M$ の2進表記における最大の桁数を $k$ とする. このとき, 次がわかる. なお, この $k$ の定め方から, $E_1, \dots, E_M$ の中に $2^{k-1}$ の位が $1$ である整数が存在することに注意する.

$E_1, \dots, E_M$ の $2^{k-1}$ の位が全て $1$ だった場合
$x=2^{k-1}$ の場合を考慮することによって, $\operatorname{calc}(E) \lt 2^{k-1}$ であることが分かる. また, XOR における桁ごとの独立性から, $E_i$ の $2^{k-1}$ の位を $0$ にした整数を $F_i$ としたとき,

$\operatorname{calc}(E_1, \dots, E_M)=\operatorname{calc}(F_1, \dots, F_M)$

である.

$E_1, \dots, E_M$ の $2^{k-1}$ の位が全て $1$ ではない場合
どのような $x$ を選んでも, $E_i \oplus x$ の $2^{k-1}$ の位が $1$ であるような整数 $i$ 及び, $0$ であるような整数 $i$ が存在することから, $\operatorname{calc}(E) \geq 2^{k-1}$ であることがわかる.

ここで, 議論のために $E_1, \dots, E_K$ の $2^{k-1}$ の位が $0$ , $E_{K+1}, \dots, E_N$ の $2^{k-1}$ の位が $1$ であるとしても問題ない. $E_{K+1}, \dots, E_N$ の $2^{k-1}$ の位を $0$ にした整数を $F_{K+1}, \dots, F_N$ とする. このとき, 次の2パターンを考えることになる.

$E_i \oplus x~(1 \leq i \leq K)$ の $2^{k-1}$ の位を $0$ にするような整数 $x$ においては $E_i \oplus x~(K+1 \leq i \leq N)$ の $2^{k-1}$ の位が $1$ になる. XOR の桁ごとの独立性から, $\operatorname{calc}(F_{K+1}, \dots, F_N)$ に帰着することができる.
$E_i \oplus x~(K+1 \leq i \leq N)$ の $2^{k-1}$ の位を $0$ にするような整数 $x$ においては $E_i \oplus x~(1 \leq i \leq K)$ の $2^{k-1}$ の位が $1$ になる. XOR の桁ごとの独立性から, $\operatorname{calc}(F_1, \dots, F_K)$ に帰着することができる.