naoya_t@topcoder

SRM381 Div1 Easy: TheDiceGame

過去問, 練習 | 20:41 |

SRM432前の準備運動に

class TheDiceGame {
 public:
  double expectedThrows(int candies) {
    int n=candies+6;
    vector<double> t(n,0.0),r(n,0.0);
    t[1]=t[2]=t[3]=t[4]=t[5]=t[6]=1.0;
    r[1]=r[2]=r[3]=r[4]=r[5]=r[6]=1.0/6;
    for(int i=1;i<candies;i++){
      double t_=t[i]+1, r_=r[i]/6;
      for(int j=1;j<=6;j++){
        double tj=t[i+j], rj=r[i+j];
        r[i+j]=r_+rj;
        t[i+j]=(t_*r_ + tj*rj)/r[i+j];
      }
    }
    double t_=0, r_=0;
    rep(i,6){
      int c=candies+i;
      t_ += t[c]*r[c]; r_ += r[c];
    }
    return t_/r_;
  }
};