結果

問題 No.76 回数の期待値で練習
ユーザー ぴろずぴろず
提出日時 2015-05-07 19:25:18
言語 Java21
(openjdk 21)
結果
AC  
実行時間 179 ms / 5,000 ms
コード長 1,289 bytes
コンパイル時間 2,071 ms
コンパイル使用メモリ 76,736 KB
実行使用メモリ 49,328 KB
最終ジャッジ日時 2024-07-05 19:52:01
合計ジャッジ時間 3,221 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 178 ms
48,924 KB
testcase_01 AC 179 ms
49,328 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

package no076a;

import java.util.Scanner;

public class Main {
	static double[] sample = {0,1.0000000000000000,1.0833333333333333,1.2569444444444444,1.5353009259259260,1.6915991512345676,2.0513639724794235};
	public static void main(String[] args) {
		double[] p = new double[7];
		double[] e = new double[1000010];
		for(int i=1;i<=5;i++) {
			double sum = 0;
			for(int j=1;j<i;j++) {
				sum += p[j];
			}
			double l = 0;
			double r = 1 - sum;
			for(int t=0;t<30;t++) {
				double c = (l + r) / 2;
				p[i] = c;
				p[i+1] = 1 - sum - c;
				simulate(e, p, i+1);
				if (e[i+1] < sample[i+1]) {
					l = c;
				}else{
					r = c;
				}
			}
		}
//		System.out.println(Arrays.toString(p));
		simulate(e, p, 1000000);
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		for(int i=0;i<t;i++) {
			int n = sc.nextInt();
			System.out.println(e[n]);
		}
	}
	static void simulate(double[] e,double[] p,int max) {
		/*
		 * e[i] := 出目の和がi以上になるまでにサイコロを振る回数の期待値
		 * (i <= 0) e[i] = 0
		 * (i > 0)  e[i] = 1 + (e[i-1] * p[1] + e[i-2]* p[2] + ... + e[i-6] * p[6]
		 */
		e[0] = 0;
		for(int i=1;i<=max;i++) {
			e[i] = 1;
			for(int j=1;j<=6;j++) {
				if (i-j < 0) {
					break;
				}
				e[i] += e[i-j] * p[j];
			}
		}
	}
}
0