No.76 回数の期待値で練習 - yukicoder
- sample からサイコロの各目が出る確率を逆算するという変わったな問題。
- サンプルを眺めるだけで各目が出る確率がわかってしまう人達もいるみたい。すげぇ。
- 下のコードは逆算を二分探索を使ってやる方法。自分でうまく実装できなかったので、editorial のコードを参照にした。
class CountExpectationPractice {
public:
void solve(void) {
int T;
cin>>T;
vector<double> ans = {0.0,
1.0000000000000000,
1.0833333333333333,
1.2569444444444444,
1.5353009259259260,
1.6915991512345676,
2.0513639724794235};
vector<double> p(6,0);
int maxN = (int)(1E+6);
vector<double> Exp(maxN+1,0);
function<void(int)> update = [&](int n) {
Exp[0] = 0;
FOR(i,1,n+1)
{
Exp[i] = 1.0;
REP(j,6)
if (i-(j+1) >= 0)
Exp[i] += Exp[i-(j+1)] * p[j];
}
};
REP(k,5)
{
double l = 0.0;
double u = 1.0;
double mid = 0.0;
REP(i,k-1)
u -= p[i];
REP(_,100)
{
p[k] = mid = (l+u)*0.5;
p[5] = 1.0;
REP(j,5)
p[5] -= p[j];
update(k+2);
if (Exp[k+2] > ans[k+2])
u = mid;
else
l = mid;
}
p[k] = mid;
p[5] = 1.0;
REP(i,5)
p[5] -= p[i];
}
update(maxN);
REP(i,T)
{
int N;
cin>>N;
cout<<setprecision(20)<<Exp[N]<<endl;
}
}
};