CS Academy Amusement Park
リンク : https://csacademy.com/contest/archive/task/amusement-park/statement/
問題概要
N*Mの行列Aが与えられる。このA[i][j]は座標(i,j)からA[i][j]の確率で座標(i,j+1)に進み、それ以外は座標(i+1,j+1)に進む。このとき、iがNになるときの移動回数の期待値を求めよ。
解説
期待値周りの計算がガッチガチの数学なので、公式の解説を読んだほうがわかりやすいかも。dp[i][j]を今の座標からNになるまでの期待値とする。
dp[0][N]=dp[0][N-1]×A[0][N-1]
dp[0][N-1]=dp[0][N-2]×A[0][N-2]......
dp[0][1]=dp[0][0]×A[0][0]
dp[0][0]=dp[0][N]×A[0][N]
となり、円のように循環になる。なので、dp[0][0]の値が求められると、すべて求められることになる。また、x=dp[0][0]とおくと、後ろから求めることにより、x=a+bxの形になるため、xが求められる。
次にdpiについて考えると、dp[i][N]=dp[i][N-1]×A[i][N-1]+dp[i-1][N-1]×(1-A[i][N-1])......となり、これもまた先ほどと同じように求められる。
int T, A; double a[1100][1100],dp[1100][1100]; int main() { cin >> T >> A; rep(i, T)rep(j, A) { cin >> a[i][j]; a[i][j] /= 100; } for (int i = 0; i<T; i++) { double sum1 = 1, sum2 = 1 + (i - 1 >= 0 ? dp[i - 1][0] * (1 - a[i][A - 1]) : 0); for (int j = A - 1; j >= 0; j--) { sum1 *= (a[i][j]); if (j != A - 1)sum2 = (1 + sum2 * (a[i][j]) + (i-1>=0?dp[i - 1][(j+1)%A] * (1 - a[i][j]):0)); } dp[i][0] = sum2 / (1-sum1); for (int j = A-1; j >=0; j--) { dp[i][j] = 1.0 + dp[i][(j+1)%A] * a[i][j] + (i - 1 >= 0 ? dp[i - 1][(j + 1) % A] * (1 - a[i][j]) : 0); } } printf("%.15f\n",dp[T-1][0]); return 0; }