Codeforces 1285D Dr. Evil Underscores (R1800)

問題

要素数 $n$ の数列 $a$ が与えられます。 $\underset{1 \leq i \leq n}{\max} (a_i \oplus X)$ としてあり得る値の最小値を求めてください。

制約

$1 \le n \le 10^{5}$
$0 \le a_i \le 2^{30}-1$

考察

$f(X)= \underset{1 \leq i \leq n}{\max} (a_i \oplus X)$ とします。 $f(X)$ の先頭桁がなるべく小さくなるようにするのがよいので、 $X$ を先頭桁から決めていきます。今 $i$ 桁目を見ているとして、次の3つの場合があります。

(1) $i$ 桁目の数が全て $0$ のとき
$X$ の $i$ 桁目を $0$ にすることで、 $f(X)$ の $i$ 桁目を $0$ にすることができます。

(2) $i$ 桁目の数が全て $1$ のとき
$X$ の $i$ 桁目を $1$ にすることで、 $f(X)$ の $i$ 桁目を $0$ にすることができます。

(3) $i$ 桁目に $0$ と $1$ の両方があるとき
$X$ の $i$ 桁目を $0と1$ のどちらにしても、 $f(X)$ の $i$ 桁目は $1$ になります。 $i$ 桁目が $0$ であるような数の集合を $S$ 、 $1$ であるような数の集合を $T$ とします。 $X$ の $i$ 桁目を $0$ にした場合、 $S$ に含まれる数と $X$ とのxorが最大値になることはないので、次の桁を決めるときは $T$ だけを考えれば良いです。同様に $X$ の $i$ 桁目を $1$ にした場合は、 $S$ だけを考えれば良いです。両方試してよかった方を選びます。

(3)で両方試すと計算量が指数爆発する気がしますが、~~各数が見られる回数は桁数に等しいので~~、図を書くと各桁ごとに $O(n)$ かかっていると分かるので、計算量は $O(n \log \max a_i)$ です。

f:id:tekihei:20200126133147j:plain

#include<bits/stdc++.h>
using namespace std;

using Lint=long long;

int rec(int pos,vector<int> &a)
{
   if(pos<0) return 0;
   vector<int> S,T;
   for(auto I:a) (~I>>pos&1? S:T).push_back(I);
   if(S.empty()) return rec(pos-1,T);
   if(T.empty()) return rec(pos-1,S);
   return (1<<pos)+min(rec(pos-1,T),rec(pos-1,S));
}

int main()
{
   int N; cin>>N;
   vector<int> a(N);
   for(int i=0;i<N;i++) cin>>a[i];
   cout<<rec(29,a)<<endl;
}