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