TopCoder SRM 386 DIv1 Easy CandidateKeys

問題

tableの列はattributeと呼ばれる。
行はentryと呼ばれる。
attributeの部分集合で、どのentryのペアについても、そのattributeのentryのうち異なるものが少なくとも一つあるものをsuper keyと呼ぶ。

super keyのうち、他のsuper keyを部分集合として含まないものをcandidate super keyと呼ぶ。
candidate super keyのうち、attributeの数が最小であるもののattributeの数および
attributeが最大のもののattributeの数を求めよ。

制約条件

tableの行≦50
tableの列≦50

方針

全列挙。

attributeの部分集合を全列挙して、それぞれsuper keyかどうかを調べる。
次に、その部分集合がsuper keyな部分集合を持たなかったら、それはcandidate super key.

ソースコード

bool ok[1<<10];

class CandidateKeys {
  public:
  vector <int> getKeys(vector <string> table) {
    int n=table.size(),m=table[0].size();
    rep(i,1<<m){
      ok[i]=1;
      rep(j,n)rep(k,j){
        bool same=1;
        rep(l,m)if(i&1<<l)if(table[j][l]!=table[k][l])same=0;
        if(same)ok[i]=0;
      }
    }
    int mx=-1,mn=inf;
    rep(i,1<<m)if(ok[i]){
      int bit=__builtin_popcount(i);
      for(int j=i;j;j=j-1&i)if(ok[i^j])goto FAIL;
      mx=max(mx,bit);
      mn=min(mn,bit); FAIL:;
    }
    vi ans;
    if(mx<0)return ans;
    ans.pb(mn); ans.pb(mx);
    return ans;
  }
};