ARC092 D : Two Sequences(500)

作成日:2018.08.15
最終更新日:2018.08.15

問題概要

問題本文

 長さ$N$の非負整数列$\{a_i\}$,$\{b_j\}$が与えられる。 $N^2$個ある$a_i + b_j$の$xor$を求めよ。
制約
$1 \leq N \leq 2 \times 10^5$
$0 \leq N \lt 2^{28}$

考え方

 $xor$を求めるので、2進数表記して桁ごとに考える。 すなわち、$a_i + b_j$の$2^k$の位が$1$となるものが何個あるかを考えれば良い。 但し、愚直にやると間に合わないので工夫する。
 $a_i,b_j$の二つが動くので、まずは$a_i$を固定して考える。 $2^k$の位が$1$になるかは、下位$(k+1)$ビットだけを見れば十分である。 下位$(k+1)$ビットの足し算の結果は$0$以上$2^{k+2}-2$以下であるから、$b_j$の下位$(k+1)$ビットが$2^k - a_i$以上$2^{k+1} - a_i$未満または$2^{k+1}+2^k - a_i$以上$2^{k+2}-2 - a_i$以下であれば良い。 このような$b_j$の個数は、下位$(k+1)$ビットでソートした数列を二分探索することで求めることができる。
 ソートすることを考えると、2進数表記した時の桁ごとに見ていくのが良い。 各桁ごとに$a_i$それぞれに対してその桁が$1$となるような$b_j$が何個あるかを求め、その個数の和の偶奇を調べれば解ける。 計算量は$O(N \: log \: N \: log \: max(a_i,b_j))$であるから十分高速である。

ソースコード

マクロ等はこちら

const int MC = 200010;
int N;
int a[MC],b[MC];

int BS(int x , int y , int t , int i){	//下位iビットがt未満であるbの数
	if(x-y<2) return x;
	int z = (x+y)/2;
	return (b[z] & (1<<i+1)-1) < t ? BS(x,z,t,i) : BS(z,y,t,i);
}

int solve(int x , int i){
	int p = (1<<i) - (x & (1<<i+1)-1);
	int q = p + (1<<i);
	return p < 0 ? N - BS(N,-1,p+(1<<i+1),i) + BS(N,-1,q,i) : BS(N,-1,q,i) - BS(N,-1,p,i);
}

int main(){
	cin >> N;
	repp(i,0,N) cin >> a[i];
	repp(i,0,N) cin >> b[i];
	int ans = 0;
	repp(i,0,29){	//足し算するから 2^29未満
		sort(b,b+N,[&](const int &x , const int &y){return (x&(1<<i+1)-1) < (y&(1<<i+1)-1);});
		repp(k,0,N) if(solve(a[k],i)&1) ans ^= 1<<i;
	}
	cout << ans << endl;
	return 0;
}

解法まとめ

 2進数表記した時の桁ごとに見ていく。(22行)
 $b_j$を今見ている桁以下の大小でソートし、各$a_i$において$b_j$の下位$(k+1)$ビットが$2^k - a_i$以上$2^{k+1} - a_i$未満または$2^{k+1}+2^k - a_i$以上$2^{k+2}-2 - a_i$以下となるような個数を求め、その個数の総和を$2$で割った余りが答えの今見ている桁となる。(5-9,11-15,23,24行)

ARC092の他の問題 C E F

広告

自己紹介

赤になりたい競技プログラマー/バランス重視
詳しくはこちら
twitter

プライバシーポリシー

個人情報利用についてはこちら

お問い合わせ

このページに関するお問い合わせはこちら

競技プログラミングMENU

問題を解くまでの道のり

その他

全体MENU

広告