CodeChef July Challenge: Parity Again

個人的に面白かったので書きます。

問題概要

原文 → Contest Page | CodeChef

整数集合 (multiset ではない set) があり、はじめは空集合である。この集合に対して以下で示すクエリを 回処理する。

• 整数 が与えられるので以下を処理
  • に を insert する
  • の元 全てに対して、 を に insert する ( は xor)
• 上の処理を行った後に、整数を 2 進数として見たときの popcount が偶数である要素の個数と、奇数である要素の個数をそれぞれスペース区切りで出力

制約

• 

解説

一見愚直では間に合わなさそうに見えるが、「 に が含まれていた場合は何もせず、含まれていない場合のみ真面目に操作」するだけで間に合う。以下にその理由を示す。

まず、問題文中の操作より以下が成り立つ。

• ある整数 についてどちらも に含まれている場合、 も に含まれている

これを踏まえると、実は以下も成り立つ。

• ある整数 が に含まれておらず、 が に含まれている場合、 は に含まれていない

背理法でこれを示す。 が に含まれていたとしよう。 も も含まれていることと、上の条件より、 が に含まれる。しかし、これは仮定に矛盾するので、 かつ であるならば である。

これを踏まえると、 が に含まれていない場合は にすでに存在する要素と xor を取ることで常に新たな要素を作ることになるし、 が含まれている場合は にすでに存在する要素と xor を取っても新たな要素が何も生まれないということになる。つまり、冒頭で示したような工夫をすることで全ての要素について高々 1 回しか生成しないようにできるため、十分高速に動作する。

ソースコード

int main() {
    int T; scanf("%d", &T);
    while(T--) {
        set<int> even, odd;
        even.emplace(0);
        int Q; scanf("%d", &Q);
        while(Q--) {
            int X; scanf("%d", &X);
            set<int> &p = (__builtin_parity(X) ? odd : even);
            if(!p.count(X)) {
                vector<int> n_even, n_odd;
                for(auto e : even) {
                    int V = e ^ X;
                    if(__builtin_parity(V)) n_odd.emplace_back(V);
                    else n_even.emplace_back(V);
                }
                for(auto e : odd) {
                    int V = e ^ X;
                    if(__builtin_parity(V)) n_odd.emplace_back(V);
                    else n_even.emplace_back(V);
                }
                for(auto e : n_even) even.emplace(e);
                for(auto e : n_odd) odd.emplace(e);
            }
            printf("%zu %zu\n", even.size() - 1, odd.size());
        }
    }
}

これ頭で考えてて解けなかったんですが、解説みてなるほどなぁってなりました。