TopCoder 練習 CandidateKeys(SRM 386 Div1 Easy)

CandidateKeys(SRM 386 Div1 Easy)

■問題
本家参照．

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

view plainprint?

1. public class CandidateKeys{  
2.  int n, m;  
3.  String[] table;  
4.  public int[] getKeys(String[] table){  
5.   n=table.length;  
6.   m=table[0].length();  
7.   this.table=table;  
8.   boolean[] candidate=new boolean[1<<m];  
9.   int min=-1, max=0;  
10.   for(int sup=0;sup<1<<m;sup++){  
11.    if(isSuperKey(sup)){  
12.     boolean f=true;  
13.     for(int sub=(sup-1)&sup;sub!=0;sub=(sub-1)&sup){  
14.      f&=!candidate[sub];  
15.     }  
16.     candidate[sup]=f;  
17.     if(f){  
18.      int bit=Integer.bitCount(sup);  
19.      if(min==-1||bit<min){  
20.       min=bit;  
21.      }  
22.      if(bit>max){  
23.       max=bit;  
24.      }  
25.     }  
26.    }  
27.    // System.out.println(Integer.toString(sup,2)+":"+isSuperKey(sup)+":"+candidate[sup]);  
28.   }  
29.   if(min==-1){  
30.    return new int[0];  
31.   }  
32.   else{  
33.    return new int[]{min, max};  
34.   }  
35.  }  
36.    
37.  boolean isSuperKey(int sup){  
38.   if(sup==0) return false;  
39.   String[] ss=new String[n];  
40.   for(int j=0;j<n;j++){  
41.    int s=sup;  
42.    ss[j]="";  
43.    for(int i=m-1;i>=0;i--){  
44.     if((s&1)==1){  
45.      ss[j]=table[j].charAt(i)+ss[j];  
46.     }  
47.     s>>=1;  
48.    }  
49.   }  
50.   for(int j=0;j<n;j++){  
51.    for(int i=j+1;i<n;i++){  
52.     if(ss[i].equals(ss[j])){  
53.      return false;  
54.     }  
55.    }  
56.   }  
57.   return true;  
58.  }  
59. }  

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