hogecoder

つたじろう(Tsuta_J) 競技プログラミングの記録

CodeChef July Challenge: Parity Again

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

問題概要

原文 → Contest Page | CodeChef

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

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

制約

  •  1 \leq Q, X \leq 10^{5}

解説

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

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

  • ある整数  x, y についてどちらも  S に含まれている場合、 x \oplus y S に含まれている

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

  • ある整数  x S に含まれておらず、 y S に含まれている場合、 x \oplus y S に含まれていない

背理法でこれを示す。 x \oplus y S に含まれていたとしよう。 y x \oplus y も含まれていることと、上の条件より、 y \oplus (x \oplus y) = x S に含まれる。しかし、これは仮定に矛盾するので、 x \notin S かつ  y \in S であるならば  x \oplus y \notin S である。

これを踏まえると、 X S に含まれていない場合は  S にすでに存在する要素と xor を取ることで常に新たな要素を作ることになるし、 X が含まれている場合は  S にすでに存在する要素と 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());
        }
    }
}

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