SRM699 Div1 Easy "OthersXor"

問題

TopCoder Statistics - Problem Statement

解法

N匹の狼がいて、何匹か飴を１つ持っている。ここで、それぞれの狼に「あなたを除く他の狼たちの飴を合計するとそれは奇数？偶数？」と聞く。狼たちは正直に答えるが、黙秘権を行使する狼もいる。この時、飴の合計の最小はいくつだ？

というような問題に置き換えられる。

「奇数です」と答えた狼がいなかったとすると、全員の狼が飴を持っていない場合で整合性がとれるため、飴の数は0でよい。

では、「奇数です」と答えた狼がいた場合はどうか？
まず、「奇数です」と答えた狼同士、もしくは「偶数です」と答えた狼同士、それら全員飴を持っているか、誰も持っていないかでなければならない。なぜなら、持っている狼と持っていない狼の合計値の差が１になってしまうため、偶奇がズレてしまうからである。なので、「奇数です」と答えた狼全員に持たせるか、「偶数です」と答えた狼全員に持たせるか、小さいほうをとればよい。

事後

難しいけど偶奇を考えるのは面白いなぁ

ソースコード

class OthersXor {
    public:
    long long minSum(vector<int> x) {
        int n = x.size();
        long long ans = 0;
        // それぞれのビット位置で回す
        for (int mask = 1; mask < 1 << 30; mask <<= 1) {
            // 奇数・偶数・黙秘の数を数え上げる
            int odd = 0;
            int even = 0;
            int unknown = 0;
            for (int i = 0; i < n; i++) {
                if (x[i] == -1) {
                    unknown++;
                } else {
                    if ((x[i] & mask) != 0) {
                        odd++;
                    } else {
                        even++;
                    }
                }
            }
            if (odd != 0) {
                // 奇数と答えた狼がいた場合
                const int INF = 50;
                int use_odd = INF;
                // 奇数組全員に持たせる場合
                if (odd % 2 == 0) {
                    use_odd = odd;
                } else if (unknown != 0) {
                    use_odd = odd + 1;
                }
                // 偶数組全員に持たせる場合
                int use_even = INF;
                if (even % 2 != 0) {
                    use_even = even;
                } else if (unknown != 0) {
                    use_even = even + 1;
                }
                // 奇数偶数小さいほうをとる
                int use_num = min(use_odd, use_even);
                if (use_num == INF) {
                    return -1;
                }
                ans += (long long)mask * use_num;
            }
        }
        return ans;
    }
};