This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.
全員が少なくとも一回は歌えるものの集合の中で，最小の要素数を答える．全ての歌を誰かしらが歌える条件での人数の最小化だと思っていて，全然ダメだった．歌は$10$までしかないので部分集合を全部列挙して，共通集合が無ければ歌えないので選べない．
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair
using namespace std ;
typedef long long ll ;
typedef pair < int , int > P ;
class CarolsSinging {
public :
int choose ( vector < string > lyrics ) {
int n = lyrics . size (), m = lyrics [ 0 ]. size ();
vector < int > v ( n );
rep ( i , n ) {
int x = 0 ;
rep ( j , m ) {
if ( lyrics [ i ][ j ] == 'Y' ) {
x |= ( 1 << j );
}
}
v [ i ] = x ;
}
int ans = INF ;
rep ( i , 1 << m ) {
bool flag = true ;
rep ( j , n ) {
if (( i & v [ j ]) == 0 ) flag = false ;
}
if ( flag ) {
ans = min ( ans , __builtin_popcount ( i ));
}
}
return ans ;
}
};