No.75 回数の期待値の問題 - yukicoder
- 自分自身を含む K+1 連立方程式を解く問題。確率系は苦手意識が...。いや、他のも解けないけど..。
- 最初なんで 2 分探索が使えるのかわからなかった。高校数学ですね...。
- いろんな解法があるらしい。引き出しが多いのはうらやましいな。
class CountExpectationProblem {
public:
double F(int K, double x) {
vector<double> Exp(K+1,0);
FOR(k,1,K+1)
{
Exp[k] = 1.0;
for (int i = 1; i <= 6; ++i)
Exp[k] += ((k-i>=0)? Exp[k-i] : x)/6.0;
}
return Exp[K];
}
void solve_binserach(void) {
int K;
cin>>K;
double low = 0.0;
double high = 10E+6;
REP(i,100)
{
double mid = (low+high)*0.5;
if (F(K, mid) > mid)
low = mid;
else
high = mid;
}
cout<<setprecision(20)<<(low+high)*0.5<<endl;
}
void solve(void) {
solve_binserach();
}
};