ARC 092 D Two Sequences - ちゃっくのメモ帳

これ500は冗談でしょ....僕が解けなかったから多分600か700あるよ

[試して理解]Linuxのしくみ ~実験と図解で学ぶOSとハードウェアの基礎知識

作者: 武内覚
出版社/メーカー: 技術評論社
発売日: 2018/02/23
メディア: 単行本（ソフトカバー）
この商品を含むブログ (1件) を見る

問題概要

長さNの数列a,bが与えられる。
この数列aとbに対して全ての $a_i+b_j$ のxorを計算せよ

解説

k-bit目(0-origin)を決める方法を考える。
k-bit目を決めるのにa[i],b[j]の0~k-bitさえ考えれば良いので、 $mod 2^(k+1)$ で考える。
$a_i+b_j$ のk-bit目が1になっているものの個数を数える。
$a_i+b_j$ でk-bit目が1になっているものは次の2パターンある $01?...?$ , $11?...?$ (k+1~0-bit目のみ記述)
前者の取りうる値は $2^k \sim 2^(k+1)-1$
(つまり、 $010...0 \sim 011...1)$ 、
後者の取りうる値は $2^(k+1) + 2^k \sim 2^(k+1) + 2^k+ 2^k - 1$
(つまり、 $110...0 \sim 111...1$ )
となる。
これを満たすような $a_i+b_j$ を探索すればよいが、aとbについてループを回すと $O(N^2)$ となるのでTLEする。
そこで $a_i$ を固定した上で、bをソートし上の条件を満たすようなbの要素の境界を二分探索で探し個数を数えればよい。

int N;
vector<int> a,b;

int main(){
    cin >> N;
    a.resize(N);
    b.resize(N);
    rep(i,N) cin >> a[i];
    rep(i,N) cin >> b[i];

    int ans = 0;
    rep(k,29){
        int T = (1 << k);
        vector<int> B(N);
        rep(i,N) B[i] = b[i] % (1<<(k+1));
        sort(all(B));
        int cnt = 0;
        rep(i,N){
            int A = a[i] % (1<<(k+1));
            int idx1 = lower_bound(B.begin(),B.end(),T-A) - B.begin();
            int idx2 = lower_bound(B.begin(),B.end(),2*T-A) - B.begin();
            int idx3 = lower_bound(B.begin(),B.end(),3*T-A) - B.begin();
            int idx4 = lower_bound(B.begin(),B.end(),4*T-A) - B.begin();
            cnt += idx2-idx1;
            cnt += idx4-idx3;
        }
        if(cnt%2){
            ans |= (1<<k);
        }
    }
    cout << ans << endl;
}