SRM 488 div1 easy: TheBoredomDivOne

問題

TopCoder Statistics - Problem Statement

解法

dp[n][m] = (退屈な人が n 人, そうでない人が m 人である際に, すべての人が 退屈になるのにかかる時間) とすると, 以下のような漸化式が成り立ちます。

dp[n][m] = ((1+dp[n][m]) + (1+dp[n+1][m-1]) + (dp[n+2][m-2]+1))

dp[n][m] は左辺に持って行くようにして dp[n][m] を再帰的に求めていけば OK です。

解き方すぐわかったのに実装に時間がかかった…

double dp[100][100];

double dfs(int n, int m) {
    double& ret = dp[n][m];
    if (ret >= 0) return ret;
    ret = 0;
    if (m == 0) return ret;
    int nmc2 = (n+m)*(n+m-1)/2;
    int mc2 = m*(m-1)/2;
    int nc2 = n*(n-1)/2;
    if (n < 2) {
        if (m > 0) ret += 1.*n*m/nmc2 * (1+dfs(n+1, m-1));
        if (m > 1) ret += 1.*mc2/nmc2 * (1+dfs(n+2, m-2));
    } else {
        ret += 1.*nc2/nmc2;
        if (m > 0) ret += 1.*n*m/nmc2 * (1+dfs(n+1, m-1));
        if (m > 1) ret += 1.*mc2/nmc2 * (1+dfs(n+2, m-2));
        double p = 1.*nc2/nmc2;
        ret /= 1-p;
    }
    return ret;
}

class TheBoredomDivOne {
public:
    double find(int n, int m) {
        for (int i = 0; i < 100; i++) for (int j = 0; j < 100; j++) {
            dp[i][j] = -1;
        }
        return dfs(n, m);
    }
};