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

Source

ニコニコミュニティ
問題文

問題概要

普通のサイコロを何回か振って，出目の和をちょうど $K$ にしたい．
ただし，$K$ を超えてしまったら和を $0$ にリセットして，何回でも，やり直す．（振った回数はリセットされない）
何回振ることになるか期待値を求める問題．

解法

色々解法はあるが，例えば，二分探索できる．
答えの候補を $c$ として，$K$ を超えたら，これから $c$ 回振れば辿り着くと仮定してDPする．
そして，DPで求まった答えが $c$ 以下（以上）なら，本当の答えは $c$ 以下（以上）であることがわかる．
それを用いて二分探索すれば，要求精度を $\varepsilon$ とすれば，時間計算量は $O(N \log (1/\varepsilon))$．
または，リセットする確率，リセットされない場合に必要な回数の期待値を求めてそこから計算しても良い．
これだと，時間計算量 $O(N)$．

後は，今の目の和を状態として，各状態からゴールするまでのサイコロを振る回数の期待値を連立一次方程式を立てて求める．
ガウスジョルダンすれば，時間計算量は $O(N^3)$ で，ガウスザイデルみたいに収束するまでループしても良い．
要求誤差が緩いので，モンテカルロしても通る．

C++によるスパゲッティなソースコード

#include<bits/stdc++.h>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar_unlocked()

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}

int main(){
  int i, j, loop, N;
  double a, b, c;
  double dp[1000];

  reader(&N);
  a = 0; b = 1000;
  rep(loop,200){
    c=(a+b)/2;
    dp[0] = 0;
    REP(i,1,N+1){
      dp[i] = 1;
      rep(j,6) dp[i] += ((i-1-j>=0)?dp[i-1-j]:c)/6;
    }
    if(dp[N] > c) a = c; else b = c;
  }
  printf("%.10f\n",(a+b)/2);
  

  return 0;
}

Current time: 2024年04月26日17時33分22秒
Last modified: 2014年11月24日00時22分03秒 (by laycrs)
Tags: Competitive_Programming yukicoder
トップページに戻る

Logged in as: unknown user (not login)

ログイン：