AtCoder ARC #122 (東京海上日動 プログラミングコンテスト2021) : D - XOR Game

実装は手間だけど、考察は割とあっさり。
https://atcoder.jp/contests/arc122/tasks/arc122_d

問題

2N個の整数がある。
先手がそこから1要素を取り除き、後手がまた1要素取り除いたとする。この時取り除いた値のペアを覚えておく。
この処理を最後まで行ったとき、ゲームのスコアは各手順におけるペアの両値のxorの最大値とする。

先手はスコアを最大化、後手は最小化しようとするとき、スコアはどうなるか。

解法

後手が、最初に「先手のどの値に対し、どの値をぶつける」と決めてしまえば、先手がどの順番で要素を選ぶかはどうでもよい(常に後手が対応する値をぶつければよい)。

後手はスコアを最小化しようとするので、先手に対しMSBが一致するものをぶつけようとするはずである。
そこで、整数値の集合Sに対し、上のbitから以下のように処理する。

今d bit目を見ているとする。
Sのうち、d bit目が立っているものをA、そうでないものをBとする。
A,Bそれぞれ偶数なら、後手は常にd bit目が一致するものをぶつけられるので、AとBそれぞれ(d-1)bit目に対する処理を再帰的に行い、その大きい方が解になる。
そうでない場合、AのうちどれかはBのうちどれかとぶつけなければならない。
xorを取ったとき、d bit目が立つのはしょうがないので、それ以外を最小化することを考える。
これはTrieを作っておけばO(|S|*d)程度で判定できる。

int N;
int A[402020];

struct BinarySumTrie {
	BinarySumTrie *nex[2];
	ll v;
	BinarySumTrie() {
		nex[0]=nex[1]=NULL;v=0;
	}
	void add(ll s,ll val,int pos=29) {
		v += val;
		if(pos>=0) {
			int c=(s>>pos)&1;
			if(!nex[c]) nex[c]=new BinarySumTrie();
			nex[c]->add(s,val,pos-1);
		}
	}
	int pick(ll val,int pos=29) { // sum [0,s-1]
		if(pos<0) return 0;
		
		int tar=0;
		if(val&(1LL<<pos)) {
			if(nex[1]&&nex[1]->v) tar=1;
			else tar=0;
		}
		else {
			if(nex[0]&&nex[0]->v) tar=0;
			else tar=1;
		}
		return (tar<<pos)+nex[tar]->pick(val,pos-1);
	}
};

BinarySumTrie root;


int dfs(vector<int> V,int d) {
	vector<int> A,B;
	if(V.size()==0) return 0;
	if(d<0) return 0;
	
	FORR(v,V) {
		if(v&(1<<d)) A.push_back(v^(1<<d));
		else B.push_back(v);
	}
	
	if(A.size()%2==0 && B.size()%2==0) {
		int a=dfs(A,d-1);
		int b=dfs(B,d-1);
		return max(a,b);
	}
	else {
		BinarySumTrie root;
		FORR(a,A) root.add(a,1);
		int mi=1<<30;
		FORR(b,B) {
			int x=root.pick(b);
			mi=min(mi,(b^x)|(1<<d));
		}
		return mi;
	}
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	vector<int> V;
	FOR(i,2*N) {
		cin>>x;
		V.push_back(x);
	}
	
	
	
	cout<<dfs(V,29)<<endl;
	
	
}

まとめ

CodeforcesやCSAcademyで多そうな問題。