はまやんはまやんはまやん

hamayanhamayan's blog

Two Sequences [AtCoder Regular Contest 092 D]

https://beta.atcoder.jp/contests/arc092/tasks/arc092_b

解法

https://beta.atcoder.jp/contests/arc092/submissions/2219193

最終的なXORを答える問題でよくある方針として「各ビット毎に立つか立たないかを決定する」という方針がある。
なので「check(d) := 下d桁目が1になるか」を計算しよう。
大まかな方針は「下d桁目が1となる和の組み合わせ数を計算することで判定」である。
下d桁目が1になるにはxorなので、下d桁目が1となる和の組み合わせ数が奇数となる必要がある。
そのため、組み合わせ数を数えて奇数ならreturn 1、偶数ならreturn 0とすればいい。
では、その組み合わせ数を考えていこう。
 
数える為に「配列Aの要素を全探索して下d桁目が1となる配列Bの要素の個数を数える」ことにする。
足してd桁目がどうだという話なので、配列Aも配列Bも(d+1)桁目以上はこの判定には必要ない。
よって、2^(d+1)で全て剰余を取った状態で考えよう。
配列Aの要素で全探索するが、A[i]のd桁目が1かそうでないか、B[i]のd桁目が1かそうでないかで処理を分ける。
 
A[i]のd桁目が1でB[i]のd桁目が1の場合
(A[i] - 2^d) + (B[i] - 2^d)をした時に繰り上がりが発生する必要がある。
A[i]を固定した時に使えるB[i]は、「2^d - (A[i] - 2^d) ≦ B[i] - 2^d」を満たすものである。
これを高速に計算するために「BB[i] := d桁目がiの時のB[i] % (2^d)の数の集合」を用意しよう。
BB[1]の中で(2^d - (A[i] - 2^d))以上の個数を数えれば良く、BB[i]がソートされていれば二分探索で高速に数えられる。
 
残りは、
A[i]のd桁目が1でB[i]のd桁目が0の場合 -> 繰り上がりしない
A[i]のd桁目が0でB[i]のd桁目が1の場合 -> 繰り上がりしない
A[i]のd桁目が0でB[i]のd桁目が0の場合 -> 繰り上がり発生
で同様に数え上げる。
 
O(30NlogN)

int N, A[201010], B[201010];
//---------------------------------------------------------------------------------------------------
int AA[201010];
int check(int d) {
    int msk = 1 << d;
    rep(i, 0, N) AA[i] = A[i] % (msk * 2);
 
    vector<int> BB[2];
 
    rep(i, 0, N) {
        int b = B[i] % (msk * 2);
 
        if (b & msk) BB[1].push_back(b - msk);
        else BB[0].push_back(b);
    }
 
    rep(i, 0, 2) sort(all(BB[i]));
 
    ll cnt = 0;
    rep(i, 0, N) {
        if (AA[i] & msk) {
            int a = AA[i] - msk;
 
            // 繰り上がりダメ
            int c = lower_bound(all(BB[0]), msk - a) - BB[0].begin();
            cnt += c;
 
            // 繰り上がりする
            c = lower_bound(all(BB[1]), msk - a) - BB[1].begin();
            cnt += BB[1].size() - c;
        } else {
            int a = AA[i];
 
            int c = lower_bound(all(BB[0]), msk - a) - BB[0].begin();
            cnt += BB[0].size() - c;
 
            c = lower_bound(all(BB[1]), msk - a) - BB[1].begin();
            cnt += c;
        }
    }
 
    if (cnt % 2 == 1) return 1;
    else return 0;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N) cin >> B[i];
 
    int ans = 0;
    rep(d, 0, 29) if (check(d)) ans += 1 << d;
    cout << ans << endl;
}