SRM 331 DIV1 Easy - CarolsSinging (復習×○)

February 21, 2014

問題

http://community.topcoder.com/stat?c=problem_statement&pm=7280&rd=10011

一つの歌をみんなで歌いたいが、それぞれの人で覚えている箇所が違う。
このとき、みんなが少なくとも１箇所歌える最小の歌詞の長さを求める。

解き方

歌詞の長さは１０なので、全探索可能。
ビットマスクを利用して全探索する。

コード

using namespace std;

#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()

class CarolsSinging {

public:
int choose(vector<string> lyrics) {
int n=lyrics[0].size();
int ret=1e+9;

for(int i=0;i<(1<<n);i++){
int cnt=0;
vector<int> p(n,0);
for(int j=0;j<n;j++){
if(i&(1<<j)){
cnt++;
p[n-j-1]=1;
}
}

int valid=1;
FORE(i,0,lyrics.size()){
int tmp=0;
FORE(j,0,n)if(lyrics[i][j]=='Y'&&p[j])tmp=1;
valid&=tmp;
}
if(valid)ret=min(ret,cnt);
}
return ret;
}

};

using namespace std;

#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()

class CarolsSinging {

public:

int choose(vector<string> lyrics) {
int n=lyrics[0].size();
int ret=n;

for(int i=0;i<(1<<n);i++){
int valid=1;
FORE(j,0,lyrics.size()){
int mask=0;
FORE(k,0,n)if(lyrics[j][k]=='Y')mask|=(1<<k);
if((i&mask)==0)valid=0;
}
if(valid){
int cnt=0;
FORE(j,0,n)if(i&(1<<j))cnt++;
ret=min(ret,cnt);
}
}

return ret;
}

};