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行)