Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-10SRM380,SRM381,SRM382 (Practice)

SRM 381 TheDiceGame

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

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

  • あ、Theの人だ(Vasyl回)
  • 方針を検討
    • 数学ゲーと思いきや、制約ゆるい(N <= 1,000,000)のでDPしようかな
    • メモ化再起で書くとStack Overflowしそうなのでループで書く
  • 実装
    • もらうDPをループで書くのに慣れてなくてしばらく戸惑う・・・
      • メモ化再帰で書けるなら直感的にかけて好きなのに
  • サンプル通った
    • 最大ケースでチェック。提出
import java.util.Arrays;

public class TheDiceGame {
	public double expectedThrows(int candies) {
		double[] dp = new double[1000010];
		double p = 1.0d / 6;

		for (int n = 0 ; n <= candies ; n++) {
			for (int a = 1 ; a <= 6 ; a++) {
				if (n - a >= 1) {
					dp[n] += (dp[n-a] + 1.0d) * p;
				} else {
					dp[n] += p;
				}
			}
		}
		return dp[candies];
	}
}