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;
}