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;
}