Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-08SRM386 (Practice)

SRM 386 CandidateKeys

|  SRM 386 CandidateKeys - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 386 CandidateKeys - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=8444

  • 方針を検討
    • column <= 10か・・・ 普通にsuperkeyかどうかを全探索かな
      • 全探索後、各superkeyについてcandidateかどうかsubsetを取りながら調べる
    • 計算量は 2^10 * 50 * 10 + (2^10)^2 = 1,500,000ぐらい 意外と大丈夫だ
  • 実装
  • サンプル通らない。
    • あれ
    • 最大値の更新が間違ってた・・・ ここで5分ほどロスする
  • 念のため、50x10の最大ケースでテスト。
    • OK
  • 提出

import java.util.HashSet;
import java.util.Set;

public class CandidateKeys {

	public int[] getKeys(String[] table) {
		int col = table[0].length();
		int row = table.length;
		
		boolean[] issuperkey = new boolean[1<<col];
		for (int p = 1 ; p < (1<<col) ; p++) {
			if (issuperkey[p]) {
				continue;
			}
			Set<String> made = new HashSet<String>();
			boolean isok = true;
			for (int r = 0 ; r < row ; r++) {
				String entry = "";
				for (int z = 0 ; z < col ; z++) {
					if ((p & (1<<z)) >= 1) {
						entry += table[r].charAt(z);
					}
				}
				if (made.contains(entry)) {
					isok = false;
					break;
				}
				made.add(entry);
			}
			if (isok) {
				issuperkey[p] = true;
				for (int pl = p+1 ; pl < (1<<col) ; pl++) {
					if ((pl & p) >= p) {
						issuperkey[pl] = true;
					}
				}
			}
		}
		
		int min = 99;
		int max = -1;
		for (int p = 1 ; p < (1<<col) ; p++) {
			if (issuperkey[p]) {
				boolean isok = true;
				for (int sub = (p - 1) & p ; sub >= 1 ; sub = (sub - 1) & p) {
					if (issuperkey[sub]) {
						isok = false;
						break;
					}
				}
				if (isok) {
					int bc = Integer.bitCount(p);
					min = Math.min(min, bc);
					max = Math.max(max, bc);
				}
			}
		}
		if (max == -1) {
			return new int[]{};
		}
		
		
		return new int[]{min, max};
	}

}