yukicoder 0130 XOR Minimax

概要

非負整数数列 $a_1, \dots, a_n$ が与えられる. 非負整数 $x$ に対し, $f(x) = \max\{ a_1 \oplus x, \dots, a_n \oplus x\}$ とする. $\min f(x)$ を求めよ.

制約

$1 \le N \le 10^5$, $0 \le a_i \le 10^9$.

解法

$a_1, \dots, a_n$ の中に $d$ ビット目が $0$ のものも $1$ のものもあるようなもののうち, 最大の $d$ をとる. すると, どんな $x$ を取っても, $f(x)$ の $d$ ビット目は $1$ になる.

$x$ の $d$ ビット目を $0$ にすると, $f(x) = a_i \oplus x$ となる $a_i$ の候補は $d$ ビット目が $1$ のもののみで, それ以外は考慮しなくてよい.

同様に, $x$ の $d$ ビット目を $1$ にすると, $d$ ビット目が $0$ な $a_i$ のみが候補になる.

候補を絞った後は全く同じ状況になるので, 再帰すればいい.

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template<typename It>
int dfs(It b, It e, int d = 30, int offset = 0){
    if(next(b) == e) return 0;
    It m = lower_bound(b, e, offset | bit(d));
    if(e == m) return dfs(b, m, d-1, offset);
    if(b == m) return dfs(m, e, d-1, offset | bit(d));
    return min(dfs(b, m, d-1, offset), dfs(m, e, d-1, offset | bit(d))) + bit(d);
}

bool solve(){
    int n; cin >> n;
    vector<int> a(n);
    for(aur x : a) cin >> x;
    sort(all(a)); a.erase(unique(all(a)), end(a));
    cout << dfs(all(a)) << endl;
    return true;
}