yukicoder : No.130 XOR Minimax

Codeforcesにありそうだよね。
http://yukicoder.me/problems/282

問題

N要素の非負整数の数列A[i]がある。
任意の非負整数Xを選択できるとき、の最小値を求めよ。

解法

答えを上のbitから決めていく。

func(d,S)を最上位bitがd bit目以下であるような整数値の集合Sにおいて、題意のような値を返す関数とする。
A[i]≦10^9なので、func(30,(Aの各要素を含む集合))が求められればそれが答えとなる。

func(d,S)は以下のように再帰的に求められる。
まずSの要素数が1なら、XをそのSの唯一の要素にすればxorを取った値が0になるのでfunc(d,S)は0。
それ以外の場合、まずSをdビット目が0の集合T[0]と1の集合T[1]に分ける。

• T[0]が空の場合、Xのdビット目を1とすると、XとT[1]の各要素のxorを取ったとき、dビット目は0となる。
  • よってfunc(d,S)=func(d-1,(T[1]からdビット目を落としたもの))となる。
• T[1]が空の場合、Xのdビット目を0とすると、XとT[0]の各要素のxorを取ったとき、dビット目は0となる。
  • よってfunc(d,S)=func(d-1,T[0])となる。
• T[0]とT[1]がともに空でない場合、Xのdビット目を0にしても1にしても、Sの各要素とXのxorを取った値にはdビット目が1のものが登場してしまう。
  • そこで、Xのdビット目が0の時と1の時の最小値、すなわち以下の２値の小さい方を取ればよい。
    • Xのdビット目を0とすると(2^d)+func(d-1,(T[1]からdビット目を落としたもの))
    • Xのdビット目を1とすると(2^d)+func(d-1,T[0])

int N;
set<int> S;
vector<int> v;

int hoge(int d,vector<int>& v) {
	if(v.size()<=1) return 0;
	int i,j;
	vector<int> w[2];
	FOR(i,v.size()) {
		int x=v[i];
		w[(x>>d)&1].push_back(x^(x&(1<<d)));
	}
	
	if(w[0].size()==0) return hoge(d-1,w[1]);
	if(w[1].size()==0) return hoge(d-1,w[0]);
	
	return (1<<d)+min(hoge(d-1,w[0]),hoge(d-1,w[1]));
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>N;
	FOR(i,N) cin>>x, S.insert(x);
	ITR(it,S) v.push_back(*it);
	
	cout<<hoge(29,v)<< endl;
}

まとめ

久々に順調に解けた。