yukicoder No.75 回数の期待値の問題

要求誤差がゆるいのでモンテカルロ

int main(){
	int s=0,i,t,k;
	scanf("%d",&k);
	for(i=0;i<100000;i++){
		for(t=k;t;){
		//残りマス数tが0でなければ
			s++;
			t-=rand()%6+1;
			//サイコロを振って
			if(t<0)t=k;
			//行き過ぎなら振り出しに戻る
		}
	}
	printf("%f",s/1e5);
	return 0;
}

真値を求めようと思えば
「合計がK以上になるまでの期待値」÷「合計がちょうどKになる確率」で求めることができる
前者は以前やったとおりで、後者はほぼ同様に
サイコロを振っていったとき合計がちょうどkになる確率は
p[k]=(p[k-1]+p[k-2]+p[k-3]+p[k-4]+p[k-5]+p[k-6])/6
p[0]=1、k<0でp[k]=0
という漸化式で求めることができる

近似式を埋め込んで77B

n;main(){n=scanf("%d",&n)>printf("%f",n>13?n+1.66:n<7?6:n*n/9.-n*1.4+14.36);}

実質7≦k≦13の範囲さえどうにかすればいいので、わりと適当に作った

k	真値	期待値	相対誤差
1	6	6	0.00000
2	6	6	0.00000
3	6	6	0.00000
4	6	6	0.00000
5	6	6	0.00000
6	6	6	0.00000
7	9.94315	10.0044	0.00616
8	10.3517	10.2711	0.00779
9	10.8547	10.7600	0.00872
10	11.4892	11.4711	0.00157
11	12.3145	12.4044	0.00730
12	13.4318	13.5600	0.00954
13	15.0296	14.9378	0.00611
14	15.7878	15.6667	0.00767
15	16.6368	16.6667	0.00180

メモ

yukicoderでゆるふわgolf

yukicoder No.75 回数の期待値の問題