結果

問題 No.76 回数の期待値で練習
ユーザー uafr_csuafr_cs
提出日時 2015-06-08 18:00:39
言語 Java21
(openjdk 21)
結果
AC  
実行時間 1,084 ms / 5,000 ms
コード長 1,731 bytes
コンパイル時間 2,145 ms
コンパイル使用メモリ 77,948 KB
実行使用メモリ 64,108 KB
最終ジャッジ日時 2024-07-06 14:48:42
合計ジャッジ時間 3,550 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 139 ms
54,304 KB
testcase_01 AC 1,084 ms
64,108 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.Set;

public class Main {
	
	public static final int MAX = 1000000;
	
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		
		final int T = sc.nextInt();
		
		// sum(w[1 .. 6]) = 1
		
		// N = 1 -> 1.0 (定義より, w[1] + ... + w[6] = 1)
		/* N = 2 -> (1 - w[1]) * 1 + w[1] * (DP[1] + 1) = DP[2]
		 *       ->> w[1] * DP[1] + 1 = DP[2]
		 * 
		 * N = 3 -> (1 - w[1] - w[2]) * 1 + w[2] * (DP[1] + 1) + w[1] * (DP[2] + 1) = DP[3] = ...
		 *       -> 1 - w[1] - w[2] + w[2] * (DP[1] + 1) + w[1] * (DP[2]  + 1) = DP[3]
		 *       -> w[2] * DP[1] + w[1] * DP[2] + 1 = DP[3]
		 * 
		 * N = 4 -> (1 - w[1] - w[2] - w[3]) * 1 + w[3] * (DP[1] + 1) + w[2] * (DP[2] + 1) + w[1] * (DP[3] + 1)
		 *       -> w[3] * DP[1] + w[2] * DP[2] + w[1] * DP[3] + 1 = DP[4] 
		 */
		
		double[] pre_DP = new double[6 + 1];
		pre_DP[1] = 1.0000000000000000;
		pre_DP[2] = 1.0833333333333333;
		pre_DP[3] = 1.2569444444444444;
		pre_DP[4] = 1.5353009259259260;
		pre_DP[5] = 1.6915991512345676;
		pre_DP[6] = 2.0513639724794235;
		double[] weights = new double[7];
		
		double sum = 0;
		for(int i = 1; i <= 5; i++){
			double w = pre_DP[i + 1] - 1;
			
			for(int j = 1; j < i; j++){
				w -= weights[j] * pre_DP[i - j + 1];
			}
			
			weights[i] = w;
			sum += w;
		}
		weights[6] = 1 - sum;
		
		
		for(int tt = 0; tt < T; tt++){
			final int N = sc.nextInt();
			double[] DP = new double[N + 6];
			
			for(int cur = N - 1; cur >= 0; cur--){
				DP[cur] = 1;
				for(int i = 1; i <= 6; i++){
					DP[cur] += DP[cur + i] * weights[i];
				}
			}
			
			System.out.printf("%.8f\n", DP[0]);
		}
	}
	
}
0