naoya_t@topcoder

SRM386 Div1 Easy: CandidateKeys

過去問, 練習 | 17:52 |

(statistics)

問題の意味がなかなか掴めなくて悩む。

サンプルのTest Caseは通るけどシステムテストが通らない←いまここ

後でやり直そう。

class CandidateKeys {
  string mask(string orig, int m){
    char buf[11];
    int j=0;
    rep(i,orig.length()) {
      if (m==0) break;
      if (m&1) buf[j++] = orig[i];
      m/=2;
    }
    buf[j]=0;
    string s = buf;
    return s;
  }
 public:
  vector<int> getKeys(vector<string> table) {
    vector<int> ans;
    int smallest=INT_MAX, largest=0;

    int l=table[0].length();
    set<string> ts(all(table));
    int n=sz(ts); // <2-50, 1-10
    if (n==1) return ans;

    vector<int> superkeys;
    set<int> candidate_keys;
    int pmax = (1<<l)-1;
    for (int p=1;p<=pmax;p++) {
      set<string> s;
      tr(ts,it){
        s.insert(mask(*it,p));
      }
      if (sz(s)==sz(ts)) superkeys.pb(p);
    }
    for(int i=0,c=sz(superkeys); i<c; i++) {
      int pi=superkeys[i];
      int cnt=0;
      for(int j=0; j<i; j++) {
        if (i==j) continue;
        int pj=superkeys[j];
        if ((pi & pj) == pj) cnt++;
      }
      if (cnt==0) candidate_keys.insert(__builtin_popcount(pi));
    }
    if (sz(candidate_keys)==0) return ans;

    tr(candidate_keys,it){
      if(*it <smallest) smallest=*it;
      if(*it >largest) largest=*it;
    }
    ans.pb(smallest); ans.pb(largest); return ans;
  }
};