https://atcoder.jp/contests/cpsco2019-s4/tasks/cpsco2019_s4_b
解説
https://atcoder.jp/contests/cpsco2019-s4/submissions/5285048
2日を選んで会議をするが、その選び方を全探索する。
a日目とb日目の少なくともいずれかに出席可能な社員の人数が知りたい。
判定方法は色々あると思うが、ビットを用いた解法を紹介する。
これは、集合をビットに変換して考えるもので、応用が聞くので知らない場合はこの機会に覚えるといい。
集合をビットで表現するやり方がある。
「下位iビット目が1である→i番目が集合に含まれる」というルールでビットを立てる。
つまり、
{0,1,2} -> 000111 {1,3,4} -> 011010 {5} -> 100000 {} -> 000000
のような感じ。
これで「ビット列bit[d] := d日目に参加できる人の集合」を作る。
a日目とb日目の少なくともいずれかに出席可能な人の集合は、これを用いて、bit[a] | bit[b]とかける。
これはビットのOR演算であるが、各ビットで01,10,11の場合に1になるという計算でまさしく今要求されている
条件になっている。
OR演算を取って、1が立っている個数を数えると参加できる人数になる。
これは、__builtin_popcount関数を使えばいい。
注意であるが、この関数はVisualStudioで環境を揃えている場合は使えないので、
#ifdef _MSC_VER inline unsigned int __builtin_popcount(unsigned int x) { return __popcnt(x); } #endif // _MSC_VER
これでうまくやろう。
int N, D; string S[10]; int bit[10]; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N >> D; rep(i, 0, D) cin >> S[i]; rep(d, 0, D) rep(i, 0, N) if (S[d][i] == 'o') bit[d] += 1 << i; int ans = 0; rep(a, 0, D) rep(b, a + 1, D) { int bits = bit[a] | bit[b]; int tot = __builtin_popcount(bits); chmax(ans, tot); } cout << ans << endl; }