topcoder SRM 802 Div1 Medium BestEvenSplitをビットマスクの列挙で解いてみた。

問題

Nは偶数で2から30まで
N人を同人数の二つのグループにわける
友達のペアが与えられる
友達が同じグループになる個数を最大化するき、何通りのわけかたがありえるか求める

方針

30ビットは巨大だが、そのうちの15人固定なので、もしかしてビットで全部列挙できるのでは? と思ってやってみた。
前処理として、自分の友達をビットマスクで生成しておく。それにより、自分が所属するグループに友達が何人いるかビットでわかる。

実装

Nビットのうち、ちょうどKビット立っている集合を列挙する方法は蟻本p.144と、けんちょん氏のビット演算 (bit 演算) の使い方を総特集！に載っている。

inline int next_combination(int sub) {
    int x = sub & -sub, y = sub + x;
    return (((sub & ~y) / x) >> 1) | y;
}

これでやってみたところ、30ビット(10億通り)のうち15個ビットが立つのは1.5億個くらいであった。しかしループだけで4秒以上かかってしまう。(この問題は特別に制限時間が3秒に拡大されている)
その後、立っているビットと立っていないビットの数は同じなので、反転したものを使えば、半分だけ列挙すればよいことに気づいた。上の next_combination は昇順に列挙できるので、ビットマスクの値が、反転したビットマスクの値未満の間だけ列挙すればよい。すなわちビットマスクの値が2^(N-1)までを列挙する。そうすると半分の77,558,760回の処理となり、3秒でも収まるようになった。

class BestEvenSplit {
public:
    int count(int N, vector <int> X, vector <int> Y) {
        vector<int> friends(N);
        for (int i = 0; i < (int)X.size(); ++i) {
            friends[X[i]] |= 1 << Y[i];
            friends[Y[i]] |= 1 << X[i];
        }
        int ans = 0, max_count = 0;
        for (int comb = (1 << N / 2) - 1; comb < (1 << (N - 1)); comb = next_combination(comb)) {
            int cnt = 0;
            for (int i = 0; i < N; ++i) {
                // この人が所属するグループのビットマスク(combまたは~comb)を使う
                cnt += __builtin_popcount(friends[i] & ((comb & (1 << i)) ? comb : ~comb));
            }
            ans += cnt == max_count;
            if (cnt > max_count) {
                // マッチした数が最大値を超えていたら答えをリセットする
                max_count = cnt;
                ans = 1;
            }
        }
        return ans;
    }
}