Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-09SRM383,384,385 (Practice)

SRM 384 SchoolTrip

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

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

  • 方針を検討
    • また制約甘い系か・・・
    • ボールを持ってる人、生き残ってる人のビットパターンでDPしちゃおう
    • dfsで書くのが楽だよね
  • 実装
    • これ一周誰もヒットせずに同じ人に戻って来ちゃう場合もあるのか。
      • どうしよう・・・ これだとdfsが終わらない
    • しばらく考える。数式に落としてみたりとか。
      • うまくいかない・・・
  • 制約を見る。
    • ヒット率は最低でも0.1以上
    • 0.9 ^ 200 < 10^-9 だから、200回以上連続でヒットしなかった場合の確率はほぼ0で、答えの要求する精度に対して無視出来る
    • 計算量的に余裕あるし、500回以上ヒットしなかったら0を返すようにしよう
  • サンプル通った。
    • 最大ケース {10, 10, 10, 10, 10, 10} で確認
      • 0.1sで通った。余裕
  • 出した
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class SchoolTrip {

	int len;
	double[] prob;
	double[][][] memo;

	public double dfs(int now, int ptn, int cnt) {
		if (Integer.bitCount(ptn) == len - 1) {
			return 0.0d;
		}
		if (memo[now][ptn][cnt] >= 0.0d) {
			return memo[now][ptn][cnt];
		}
		if ((ptn & (1<<now)) >= 1) {
			return dfs((now+1)%len, ptn, cnt);
		}
		if (cnt >= 500) {
			return 0.0d;
		}
		
		double mintime = Double.MAX_VALUE;
		for (int t = 0 ; t < len ; t++) {
			if (t != now && (ptn & (1<<t)) == 0) {
				double proba = prob[now] * (dfs((now+1) % len, ptn | (1<<t), 0) + 1.0d);
				double probb = (1.0d - prob[now]) * (dfs((now+1) % len, ptn, cnt + 1) + 1.0d);
				mintime = Math.min(mintime, proba + probb);
			}
		}
		memo[now][ptn][cnt] = mintime;
		return mintime;
	}
	
	
	public double duration(int[] probability) {
		len = probability.length;
		prob = new double[len];
		for (int p = 0 ; p < len ; p++) {
			prob[p] = probability[p] * 1.0d / 100;
		}
		
		memo = new double[len][1<<len][501];
		for (int i = 0 ; i < len ; i++) {
			for (int j = 0 ; j < (1<<len) ; j++) {
				Arrays.fill(memo[i][j], -1.0d);
			}
		}
		return dfs(0, 0, 0);
	}
}