読者です 読者をやめる 読者になる 読者になる

Codeforces Round #383 (Div. 2) B. Arpa’s obvious problem and Mehrdad’s terrible solution

問題

Problem - B - Codeforces

考察

xorを各ペアに対して取っていく問題ですが、普通にやると間に合いません。
そこで、A xor A = 0であることを利用し、 A xor B = xの両辺にxor BをかけるとA = B xor xにすることができます。

事前にそれぞれ値の個数を算出しておくことで、前から順番に計算することができO(n)で答えが求まります。
処理方法は色々ありますが、私の場合は全てのペアで求めて最後に2で割りました。

が、底意地の悪いことにx=0が制約に入っているので、この時だけ「自分自身とのペア」を除いてあげないといけません。
また、答えはintに収まらないのでlong longにする必要があります。

↓のコードではx=0は完全に別処理にしていますが、x=0なら(a-1)*aとして逐次処理をすることでn=1の分岐も要らず、もっと綺麗に書けます。

コード

int main() {
    int n, x;
    cin >> n >> x;

    if(n == 1) {
        cout << 0 << endl;
        return 0;
    }

    map<int, int> s_nums;
    rep(i, n) {
        int t;
        cin >> t;
        s_nums[t]++;
    }

    if(x == 0) {
        ll a = 0;
        tr(it, s_nums)
            a += (ll)it->second * (it->second-1);
        cout << a / 2 << endl;
        return 0;
    }

    ll ans = 0;
    tr(it, s_nums) {
        int t = x ^ it->first;
        ans += (ll)it->second * s_nums[t];
    }

    cout << ans / 2 << endl;
    return 0;
}

感想

罠が多い……。あとタイトルが長い……。