SRM 386 250pt: CandidateKeys

TopCoder

問題概要

DBの表がある。各列の組み合わせを抽出したものが各行に対してユニークに定まるのであれば、その組み合わせを主キーと呼ぶことにする。極小な主キーの組み合わせとして、最大の数と最小の数を求める問題。行数Rは50以下、列数Cは10以下。

考えたこと

  • 問題がよく分からない。
  • しばらく経ってようやく問題を理解した。で、どうするか。
  • 主キーの組み合わせを列挙するのはO(2^C * C * R)でいける。
  • 極小の判定どうしよう。グラフ構成するのとか面倒だからやりたくない。
  • いやいや、グラフ構成する位なら候補数Nに対してO(N^2)でいけるじゃないか。
  • 後は書くだけ。サンプル通った。投げた。WA。
  • ビット回す範囲が2^Rまでになってた。2^Cに修正して無事AC。本番でこの間違いしたら悔しいだろうなあ。

practiceで通ったコード

#include <vector>
#include <string>
#include <set>
#include <algorithm>
using namespace std;

const int INF = 1<<29;

struct CandidateKeys {

	vector <int> getKeys(vector <string> table) {
		const int N = table.size(), M = table[0].length();

		vector<int> cands;

		//全通り試す
		for(int bit=0; bit<(1<<M); bit++){
			set<string> keys;

			for(int i=0; i<N; i++){
				string str;
				for(int j=0; j<M; j++)if((bit>>j)&1){
					str += table[i][j];
				}
				keys.insert(str);
			}

			if((int)keys.size() == N){
				cands.push_back(bit);
			}
		}

		if(cands.empty()){
			return vector<int>();
		}

		//極小判定
		int mi = INF, ma = 0;
		for(int i=0; i<(int)cands.size(); i++){
			bool ok = true;
			for(int j=0; j<(int)cands.size(); j++)if(i!=j){
				ok &= !( cands[i] == (cands[i] | cands[j]) );
			}

			if(ok){
				ma = max(ma, __builtin_popcount(cands[i]));
				mi = min(mi, __builtin_popcount(cands[i]));
			}
		}

		vector<int> ret(2);
		ret[0] = mi;
		ret[1] = ma;
		return ret;
	}

};