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;
}
}