Meeting [CPSCO2019 Session4 B]

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