Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-08SRM386 (Practice)

また解けるはずの問題を落としてしまった。 211/598位

問題結果ポイントその他
250CandidateKeysAccepted188.97ブルートフォース
500PolygonCoverWA0.00誤差死
1000EscapeArtistOpened0.00実装間に合わず

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

}



SRM 386 PolygonCover

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

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

  • げぇっ、幾何ゲーだ
  • 方針を検討
    • よく読むと幾何要素はそこまででもない
    • 全ての点を最低1つの多角形に使う時、面積の最小値を求める問題のようだ
    • 2分探索?いや違う。
    • 点の数が15しかないから・・・ それを使うんだろう
      • bitDPかな
    • でも計算量がヤバイ気がする
      • 三角形だけでも 2^15*(15^3) = 90,000,000ぐらい。
      • 四角形以上だと全然間に合わないだろう
  • うーん
    • 待てよ、これ作る多角形は全部三角形と仮定していいんじゃないか?
      • 任意の4点について、四角形の面積と三角形の面積x2 を比べた時、必ず 三角形x2 の面積が小さくなる作り方がある
        • 長方形の場合は特殊で、両者の面積がイコールになる
      • 5点以上についても多分同様なはず・・・
    • 三角形だけなら計算量的に余裕だろう。
  • 実装
    • dfsをゴリゴリ作る。
    • 任意の3点の三角形の面積を前計算しておこう
  • できた。サンプル通った。
    • 最大ケース(ランダム15点)でテスト。
    • OK
  • 提出
    • 直後、三点が一直線上に並ぶ場合を考慮してないことに気づく。
    • 大丈夫な気もするけど、念のため確認したい・・・
    • でも制約見ると、
      • No three points represented by x and y will lie on a common line.
    • と書いてある。よかった

システムテスト

  • WAを食らう。あれ!?
    • 誤差死してるっぽい
  • 三角形の面積の求め方。
    • ヘロンの公式を使ったが、座標が整数で与えられるときはもっと精度がいい方法が存在する!当たり前だね
    • てか |a| <= 1000 でも誤差死してしまうのか・・・
      • これは今後challengeに使えそうなので覚えておこう

import java.util.Arrays;

public class PolygonCover {
	double[] dx;
	double[] dy;

	double EPS = 0.000000001d;
	double INF = 100000000000.0d;
	double[] memo;

	double[][][] area;
	
	int len;
	
	public double area(int p1, int p2, int p3) {
	    return Math.abs((dx[p2] - dx[p1]) * (dy[p3] - dy[p1]) - (dx[p3] - dx[p1]) * (dy[p2] - dy[p1])) / 2.0d;
	}

	public double area(double ax, double ay, double bx, double by, double cx, double cy) {
		double ab = Math.sqrt((ax-bx)*(ax-bx)+(ay-by)*(ay-by));
		double bc = Math.sqrt((bx-cx)*(bx-cx)+(by-cy)*(by-cy));
		double ca = Math.sqrt((cx-ax)*(cx-ax)+(cy-ay)*(cy-ay));
		double s = (ab + bc + ca) / 2.0d;
		return Math.sqrt(s*(s-ab)*(s-bc)*(s-ca));
	}

	public double dfs(int ptn) {
		if (ptn == (1<<len)-1) {
			return 0.0d;
		}
		if (memo[ptn] < INF) {
			return memo[ptn];
		}
		
		double min = INF;
		for (int a = 0 ; a < len ; a++) {
			for (int b = a+1 ; b < len ; b++) {
				for (int c = b+1 ; c < len ; c++) {
					int nptn = ptn | (1<<a) | (1<<b) | (1<<c);
					if (ptn == nptn) {
						continue;
					}
					min = Math.min(min, area[a][b][c] + dfs(nptn));
				}
			}
		}
		memo[ptn] = Math.min(memo[ptn], min);
		return min;
	}
	
	
	public double getArea(int[] x, int[] y) {
		len = x.length;
		dx = new double[len];
		dy = new double[len];
		
		for (int i = 0 ; i < len ; i++) {
			dx[i] = x[i];
			dy[i] = y[i];
		}
		
		area = new double[len][len][len];
		for (int a = 0 ; a < len ; a++) {
			for (int b = a+1 ; b < len ; b++) {
				for (int c = b+1 ; c < len ; c++) {
					area[a][b][c] = area(a, b, c);
				}
			}
		}
		memo = new double[1<<len];
		Arrays.fill(memo, INF);
		
		return dfs(0);
	}

}


SRM 386 EscapeArtist

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

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

  • 余裕を持って1000オープン
  • 方針を検討
    • まず、エージェントが1体だけの単純な場合で考えてみよう
    • エージェントが行く各部屋番号について確率を求めておいて、最短ルートかつ確率が少ない方を選んでいけばいいか
      • 問題はその確率の求め方だ
    • (経路数) / (総経路数) でいいか
      • 最短ルートの総経路数を求め、逆にたどりながら各地点における経路数を求めていく
  • 考える
    • しかし、実際はエージェントが複数あり、しかも廊下で鉢合わせる可能性も考慮しなければならない
    • 廊下で鉢合わせるパターンは廊下もひとつのノードとして処理すればいいか
      • ノード数が結構増えてしまうけど・・・ 無理そうだったら別の方法を考えよう
    • エージェントが複数の時は?
      • 単純に確率の掛け算?
    • いや、実際はORを求めたいんだし・・・
  • 制約を見る
    • エージェント数は高々10ということに気づく。
    • それならば、蟻本に載ってた包除原理というのが使えるはずだ
    • これで大体の不安要素が解消した
  • よし、いける気がする。
  • 実装。ひたすら書く。
    • 実装量が多くて間に合う気がしない・・・
    • 時間切れ。