問題
http://community.topcoder.com/stat?c=problem_statement&pm=8444&rd=11120
解き方
ビット列ですべての組み合わせについて調べれば良い。
ただし、その部分集合で満たすものがあれば偽になるので
これまで調べたビット列で真のものを保存して、含まれないか判定する。
ビット列は順番に調べていけばそれまでの値は必ず含まれるので問題ない。
コード
class CandidateKeys {
public: vector<int> getKeys(vector<string> table) {
int n=table.size(),m=table[0].size();
int valid=0;
vector<int> ans(2);
ans[0]=1e+9,ans[1]=0;
vector<int> vx;
for(int mask=1;mask<(1<<m);mask++){
set<string> s;
FORE(i,0,n){
string str="";
FORE(j,0,m)if(mask&(1<<j))str+=table[i][j];
s.insert(str);
}
if(s.size()==n){
valid=1;
int can=1;
FORE(i,0,vx.size())if((vx[i]&mask)==vx[i])can=0;
if(can){
ans[0]=min(ans[0],__builtin_popcount(mask));
ans[1]=max(ans[1],__builtin_popcount(mask));
vx.push_back(mask);
}
}
}
return valid ? ans : vector<int>();
}
};
public: vector<int> getKeys(vector<string> table) {
int n=table.size(),m=table[0].size();
int valid=0;
vector<int> ans(2);
ans[0]=1e+9,ans[1]=0;
vector<int> vx;
for(int mask=1;mask<(1<<m);mask++){
set<string> s;
FORE(i,0,n){
string str="";
FORE(j,0,m)if(mask&(1<<j))str+=table[i][j];
s.insert(str);
}
if(s.size()==n){
valid=1;
int can=1;
FORE(i,0,vx.size())if((vx[i]&mask)==vx[i])can=0;
if(can){
ans[0]=min(ans[0],__builtin_popcount(mask));
ans[1]=max(ans[1],__builtin_popcount(mask));
vx.push_back(mask);
}
}
}
return valid ? ans : vector<int>();
}
};
Share this
Related Posts
SRM 499 DIV1 Easy - ColorfulRabbits
問題
http://community.topcoder.com/stat?c=problem_statement&pm=11327&rd=14428
様々な種類のうさぎがいる。
そのうちいくつかのうさぎに質問し- SRM 516 DIV1 Easy - NetworkXOneTimePad
問題
http://community.topcoder.com/stat?c=problem_statement&pm=10846&rd=14541
解き方
すべての暗号前の文字と暗号後の文字の組み合わ
- SRM 662 DIV1 Easy - FoxesOfTheRoundTable
問題
http://community.topcoder.com/stat?c=problem_statement&pm=13858&rd=16511
解き方
Dが1000までなので、Dを固定することで解
- SRM 539 DIV1 Easy - Over9000Rocks
問題
http://community.topcoder.com/stat?c=problem_statement&pm=11855&rd=14731
解き方
９０００以上となる数をすべて保存しては間に合