TopCoder 練習 CandidateKeys(SRM 386 Div1 Easy)

CandidateKeys(SRM 386 Div1 Easy)

■問題
本家参照．

■解法
ある列群がcandidate superkeyであるかどうかは，以下を判定すれば良い．
・その列群がsuperkeyである
・その列群の真部分集合の全要素がcandidate superkeyでない
superkeyかどうかの判断は，愚直に実装すればOK．
部分集合のビット演算は，「蟻本」の助けを借りました…．

public class CandidateKeys{
 int n, m;
 String[] table;
 public int[] getKeys(String[] table){
  n=table.length;
  m=table[0].length();
  this.table=table;
  boolean[] candidate=new boolean[1<<m];
  int min=-1, max=0;
  for(int sup=0;sup<1<<m;sup++){
   if(isSuperKey(sup)){
    boolean f=true;
    for(int sub=(sup-1)&sup;sub!=0;sub=(sub-1)&sup){
     f&=!candidate[sub];
    }
    candidate[sup]=f;
    if(f){
     int bit=Integer.bitCount(sup);
     if(min==-1||bit<min){
      min=bit;
     }
     if(bit>max){
      max=bit;
     }
    }
   }
   // System.out.println(Integer.toString(sup,2)+":"+isSuperKey(sup)+":"+candidate[sup]);
  }
  if(min==-1){
   return new int[0];
  }
  else{
   return new int[]{min, max};
  }
 }
 
 boolean isSuperKey(int sup){
  if(sup==0) return false;
  String[] ss=new String[n];
  for(int j=0;j<n;j++){
   int s=sup;
   ss[j]="";
   for(int i=m-1;i>=0;i--){
    if((s&1)==1){
     ss[j]=table[j].charAt(i)+ss[j];
    }
    s>>=1;
   }
  }
  for(int j=0;j<n;j++){
   for(int i=j+1;i<n;i++){
    if(ss[i].equals(ss[j])){
     return false;
    }
   }
  }
  return true;
 }
}