Codeforces ECR #152 : F. XOR Partition

これは丁寧に詰めて行けば解けるのか…？
https://codeforces.com/contest/1849/problem/F

問題

整数集合Sのコストは、2値のxorの最小値とする。
ただし|S|が2未満の場合、無限大とする。

互いにdistinctな値を取る整数列Aが与えられる。
これを2つの集合S1,S2に分割したい。S1とS2のコストの最小値が最小化されるような分割を答えよ。

解法

EditorialではなくEditorialページのコメント欄を参考にした。

S

が2の場合は自明なので、

S

が3以上の場合を考える。

Aのうち、leading zeroを含めた2進数表現のprefixが一致する値が3つ以上ある最長のprefixを考える。
このprefix長をLとする。
この3値を2つの集合に分けると、どちらかには2つ以上の値が入るので、コストの最小値の上位L bitは0にできる。

また、その場合prefixが一致するものは高々4つしかない。
あとはその3つないし4つの分け方を総当たりすればよい。

int N;
ll A[202020];
int ret[202020];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	
	if(N==2) {
		cout<<"10"<<endl;
		return;
	}
	int mi=32;
	map<ll,vector<int>> V;
	FOR(i,32) {
		V.clear();
		FOR(j,N) {
			V[A[j]>>i].push_back(j);
			if(V[A[j]>>i].size()>=3) mi=i;
		}
		if(mi==i) break;
	}
	
	FORR2(a,b,V) {
		if(b.size()==2) {
			ret[b[1]]=1;
		}
		else if(b.size()==3) {
			if((A[b[0]]^A[b[1]])>(A[b[0]]^A[b[2]])&&(A[b[0]]^A[b[1]])>(A[b[1]]^A[b[2]])) {
				ret[b[2]]=1;
			}
			else if((A[b[0]]^A[b[2]])>(A[b[1]]^A[b[2]])) {
				ret[b[1]]=1;
			}
			else {
				ret[b[0]]=1;
			}
		}
		else if(b.size()==4) {
			int x=0,y,aa,bb;
			int best=-1;
			ll v=-1;
			for(y=1;y<4;y++) {
				for(aa=1;aa<4;aa++) {
					for(bb=aa+1;bb<4;bb++) {
						if(aa==y||bb==y) continue;
						if(min(A[b[x]]^A[b[y]],A[b[aa]]^A[b[bb]])>v) {
							best=y;
							v=min(A[b[x]]^A[b[y]],A[b[aa]]^A[b[bb]]);
						}
					}
				}
			}
			for(i=1;i<4;i++) if(i!=best) ret[b[i]]=1;
		}
	}
	FOR(i,N) cout<<ret[i];
	cout<<endl;
	
	
}

まとめ

シンプルな解法でいいな。