yukicoder : No.2977 Kth Xor Pair

結果的にコードが短くなった。
https://yukicoder.me/problems/no/2977

問題

N要素の整数列Aが与えられる。
うち2要素のxorで得られる値のmultisetにおいて、K番目に小さい物を求めよ。

解法

上のbitから確定させていく。
今見ているbitが0となるケースがK通り以下なら0、そうでないなら1となるように値を定めて行く。

int N;
ll K;
int A[202020];
unordered_map<int,int> M;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) cin>>A[i];
	
	int ret=0;
	for(i=29;i>=0;i--) {
		ll C[2]={};
		M.clear();
		
		FOR(j,N) {
			int v=(A[j]>>i<<i);
			if(M.count(v^ret)) C[0]+=M[v^ret];
			if(M.count(v^ret^(1<<i))) C[1]+=M[v^ret^(1<<i)];
			M[v]++;
		}
		if(C[0]<K) {
			K-=C[0];
			ret|=1LL<<i;
		}
		
	}
	cout<<ret<<endl;
	
	
}

まとめ

これ系、解法は割と自明だけど実装を綺麗にしようとすると迷う。