期待値DP. 素直に考えると再帰になる． 再帰で考えた後に，高速化として for などが可能か考えればよい． 最初から綺麗に書こうとしない方が楽．
残り \(x\) ターンのときの答えを \(f(x)\) とおく．
\(f(x) = \sum_{d \in [1,6]} \frac{1}{6} max(d, f(x-1))\)
\(f(0) = 0\)
となる． ここで，\(f(0)\) はサイコロの任意の目より小さければ何でもよい． \(max(d, f(0))\) の部分で \(d\) が採用されれば何でも良いから．
または，\(f(0)\) を考えるのが心配なら \(f(1) = 7/2\) を直接求めて使っても良い．
注意
再帰の場合はメモ化しないと TLE.
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n; cin >> n;
double dp = 0.0;
rep1(i,n) {
double old = 0.0;
swap(dp, old);
rep1(j,6){
dp += max((double)j, old);
}
dp /= 6.0;
}
printf("%.10lf", dp);
return 0;
}
