読者です 読者をやめる 読者になる 読者になる

メモ

yukicoderで遊んでいる競プロゆるふわ勢

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

問題はこちら
No.75 回数の期待値の問題 - yukicoder

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

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