AtCoder ABC #304 (東京海上日動プログラミングコンテスト2023) : G - Max of Medians

うーむ、概ね方針は合っていたが、詰め切れず…。
https://atcoder.jp/contests/abc304/tasks/abc304_g

問題

2N個の整数が与えられる。
2個ずつ組を作ってそれぞれxorを取った値に置き換えると、N個の整数ができる。
これらの中央値の最大値を求めよ。

解法

中央値Mを二分探索することを考えると、2N個の整数からxorがM以上となる値がfloor*1以上のものが最大何個できるか。
G(d,C,D,M) := 数列C,Dの各要素は2^(d+1)未満とする。Cの要素とDの要素を組み合わせていくつか組を作ったとき、M%(2^(d+1))以上のものが最大何個できるか。

あとはMの2^dの桁及びC,Dの2^dの桁の0/1に応じ、xorがM%(2^(d+1))を超えるケースを丁寧に数え上げて行こう。

int N;

int G(int d,int v,vector<int>& A,vector<int>& B);
int F(int d,int v,vector<int>& A) {
	if(A.empty()) return 0;
	if(d<0) {
		return A.size()/2;
	}
	vector<int> B,C;
	FORR(a,A) {
		if(a&(1<<d)) C.push_back(a^(1<<d));
		else B.push_back(a);
	}
	if(v&(1<<d)) {
		return G(d-1,v,B,C);
	}
	else {
		if(B.size()>C.size()) swap(B,C);
		return B.size()+min((int)(C.size()-B.size())/2,F(d-1,v,C));
	}
	
}
int G(int d,int v,vector<int>& A,vector<int>& B) {
	if(A.empty()&&B.empty()) return 0;
	if(d<0) {
		return min(A.size(),B.size());
	}
	vector<int> C[2],D[2];
	FORR(a,A) C[(a>>d)%2].push_back(a&((1<<d)-1));
	FORR(a,B) D[(a>>d)%2].push_back(a&((1<<d)-1));
	
	if(v&(1<<d)) {
		return G(d-1,v,C[0],D[1])+G(d-1,v,C[1],D[0]);
	}
	else {
		if(C[0].size()>D[1].size()) swap(C[0],D[1]),swap(C[1],D[0]);
		
		if(C[1].size()<=D[0].size()) {
			return C[0].size()+C[1].size();
		}
		else {
			return C[0].size()+D[0].size()+min({(int)C[1].size()-(int)D[0].size(),(int)D[1].size()-(int)C[0].size(),G(d-1,v,C[1],D[1])});
		}
	}
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	vector<int> A(2*N);
	FORR(a,A) cin>>a;
	sort(ALL(A));
	int ret=0;
	for(i=29;i>=0;i--) {
		if(F(29,ret+(1<<i),A)>=(N+1)/2) ret+=1<<i;
	}
	cout<<ret<<endl;
}

まとめ

本番、再帰が2通りの関数に分岐するところまでは行ったけど、その後細かい部分が詰められなかったのが残念。

*1:N+1)/2)個以上作れるかという問題になる。 以下の関数を考える。 F(d,C,M) := 数列Cの各要素は2^(d+1)未満とする。これらのうちいくつか組を作ったとき、M%(2^(d+1