GCJ APAC Semifinal 2008 C問題

GCJ Round2に向けて。練習。
Dashboard - APAC Semifinal 2008 - Google Code Jam

これはぱっと見、むずい。賭ける額は小数もありなので全探索も無理。
そもそも二つ目の例のM=3、P=0.75、X=600000がなぜ0.843750となるかが不明。
1回目のbetでどうすればよいかわからない。なんか次の回の1/2が重要な気がするのだが。。

といってしばらく考えたがやはりよくわからないので小さな数で地道に実験。
まずM=1から。ふむ、0万〜50万、50万〜100万、100万〜でそれぞれ最適な策は1通りに決まる。これは優しい。
M=2はM=1とにらめっこしながらやると、M=1の場合で場合分けした区間のそれぞれ半分の区間ごとに考えれば良いことがわかる。同様にして、M=MとM-1で再帰的に考えてあげれば良い。つまり、Mがなんであれ、同一区間内の場合最終的にクリアする可能性は一定なのだ!

M=1から順に考えて動的計画法で書いてあげれば以下のようになる。とてもシンプルで素敵。
Millionaire.java

public class Millionaire
{
	static final Scanner sc = new Scanner(System.in);
	static int M;
	static double P;
	
	public static void main(String[] args)
	{
		int T = sc.nextInt();
		for(int t=1;t<=T;t++)
		{
			System.out.print("Case #"+t+": ");
			M = sc.nextInt();
			P = sc.nextDouble();
			int amount = sc.nextInt();
			System.out.println(compute(amount));
		}
	}
	
	public static double compute(int amount){
		int n = 1<<M;
		double[] prev = new double[n + 1];
		double[] next = new double[n + 1];
		
		Arrays.fill(prev,0.0);
		prev[n] = 1.0;
		
		for(int i = 0;i< M;i++)
		{
			for(int j = 0;j<= n;j++){
				next[j] = Double.MIN_VALUE;
				for(int k = 0;k<= min(j,n - j);k++)
					next[j] = Math.max(next[j], (1 - P) * prev[j-k] + P * prev[j+k]);
			}
			prev = Arrays.copyOf(next, n + 1);
		}
		
		return next[(int)(amount / 1000000.0 * n)];
	}
	
}

Dashboard - APAC Semifinal 2008 - Google Code Jamでも書いてあるように、連続で無限探索の問題が離散の問題にうまく置き換わる良問だ。どうやら日本人はこの手の問題が得意らしい。

小さな場合でしっかりと考えることが出来れば大きな問題も解決できる良い例だ。昔雲Tに教わったことやなぁーー。