Yukicoder No.301 サイコロで確率問題 (1)
Yukicoder No.75 回数の期待値の問題の制約を強めたもの。
漸化式が線形なDPなので行列化して繰り返し二乗法だろうと思ったが、誤差によりWAした。 対角化すると加算が消えて誤差が減るよと教えてもらったが、 Wolfram Alpha曰く対角化不能とのことだったので諦めた。
solution
$N \le 200$であれば、DPをすればよい。$O(N)$。 $N \gt 200$であれば、$\mathrm{ans}_n$はその収束先$n + \frac{5}{3}$にすでに十分近いので、$n + \frac{5}{3}$を出力すればよい。
DP部分に関して、これは答えを変数として持って走って再帰的な等式を作るDP。 出目の和が$N$を目指すとして、現在の出目の和が$k$である状態からのさいころを振る回数の期待値を$E_k$とする。 このとき、
- $E_k = 1 + \Sigma_{1 \le d \le 6} \frac{1}{6} E_{k+d}$ for $k \lt N$
- $E_N = 0$
- $E_k = E_0$ for $k \gt N$
という漸化式が立つ。 ここで、$E_0 = x$という変数を置くと、
- $E_k = 1 + \Sigma_{1 \le d \le 6} \frac{1}{6} E_{k+d}$ for $k \lt N$
- $E_N = 0$
- $E_k = x$ for $k \gt N$
という多項式に関する単純なDPになる。 $x$を含む式として$E_0$が求まるので、$E_0 = x$という等式を解けば答えが求まる。
implementation
#include <cstdio>
#include <vector>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define repeat_reverse(i,n) for (int i = (n)-1; (i) >= 0; --(i))
typedef long long ll;
using namespace std;
int main() {
int t; scanf("%d", &t);
while (t --) {
ll n; scanf("%lld", &n);
long double ans;
if (n <= 200) {
vector<long double> e(n+6);
vector<long double> p(n+6);
e[n ] = 0; p[n ] = 1;
e[n+1] = 0; p[n+1] = 0;
e[n+2] = 0; p[n+2] = 0;
e[n+3] = 0; p[n+3] = 0;
e[n+4] = 0; p[n+4] = 0;
e[n+5] = 0; p[n+5] = 0;
repeat_reverse (i,n) {
e[i] = 1;
p[i] = 0;
repeat (j,6) {
e[i] += e[i+1+j] / 6;
p[i] += p[i+1+j] / 6;
}
}
ans = e[0] / p[0];
} else {
ans = n + 5./3;
}
printf("%.13Lf\n", ans);
}
return 0;
}