問題はこちら
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 |