AtCoder Regular Contest 092 D - Two Sequences

「3月中に毎日1問解いて黄色になろう！」キャンペーン6問目のつもり。コンテストには参加していないので。でも、これ500はちとキツイ気がしています（個人的にEの方が簡単なので）

問題概要

N個の要素からなる数列AとBが与えられるので、for s,t in itertools.product(a,b)でのs+tの全xorを求めなさい。
N≦2×10⁵、a,b<2²⁸

D - Two Sequences

解説

普通に全部生成しても間に合いません。そこで、aとbの不思議な制約に目を付けます。ただ、2²⁸はそのまま使うには時間的にもメモリ的にも無理です。となると、2進数で桁を独立に確定していく…？となります。（従属でも考えましたが、繰り上がり処理で無限に死にます）

とにかく繰り上がりで死ぬので、それを考慮する必要のない形で考えると、「2ⁱの位を調べたいときに、Bのmod 2ⁱ⁺¹を取り、2ⁱ-a[j]よりも大きな要素は2ⁱが1になるんじゃね？」という発想が出ます（出ません）。なお、ここで2ⁱ要素の配列を用意したくなる（modの各結果に応じて）のですが、先述の通り時間もメモリも足りません。modを取ってソートしましょう。

具体的には、a[j]の2ⁱ位が1ならOKな範囲が2つに分かれるので、その両方を考える必要があります。0の時は2ⁱ-a[j]～2ⁱ⁺¹-1-a[j]まで、1の時はそれに加えて3×2ⁱ-a[j]～4×2ⁱ-1-a[j]までのb[j]の個数が1となる個数で、この個数が全体で奇数なら2ⁱは1で、そうでなければ0です。これらはlower_boundで位置を探して、イテレータの差を取ればO(logN)で算出できます。

これで、各jについてa[j]と対応する個数がO(logN)で求まり、各桁O(NlogN)で求まります。

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

int main() {
    int n; cin >> n;
    vector<int> a(n), b(n);
    rep(i, n)   cin >> a[i];
    rep(i, n)   cin >> b[i];
    sort(all(a));
    sort(all(b));
    int ret = 0;
    vector<int> amod(n), bmod(n);
    rep(i, 29) {
        rep(j, n)   amod[j] = a[j] % (2 << i);
        rep(j, n)   bmod[j] = b[j] % (2 << i);
        sort(all(bmod));
        int cnt = 0;
        rep(j, n) {
            if (amod[j] & (1 << i)) {
                // ooxxxxxxoo
                cnt += lower_bound(all(bmod), (2 << i) - amod[j]) - bmod.begin();
                cnt += bmod.end() - lower_bound(all(bmod), (3 << i) - amod[j]);
            }
            else {
                // xxxxoooooxx
                auto s = lower_bound(all(bmod), (1 << i) - amod[j]);
                auto t = lower_bound(all(bmod), (2 << i) - amod[j]);
                cnt += t - s;
            }
        }
        ret ^= ((cnt&1) << i);
    }
    cout << ret << endl;
    return 0;
}

感想

頭が無い。頭が欲しい。