SRM 504.5 div1 hard:TheTicketsDivOne

これ解けなかったの若干悔しいかもしれない。

問題

TopCoder Statistics - Problem Statement

解法

単純に再帰関数書こうとすると

dfs(n, m) -> dfs(n, m-1) -> ... dfs(n, 1) -> dfs(n, n-1) -> ... -> dfs(n, m)

みたいな感じになってぐるぐる回るので死亡する。しかし,このように依存関係があるということは,連立方程式を解けば良いだけということである。

連立方程式を解くための手段の1つとして,Gauss Seidel法がある。
Gauss Seidel法は,実際に行列の形にする必要はなくて,答えを求めるための演算を何回も繰り返しているだけで良いので実装もラク。

const int MAXN = 1001;

class TheTicketsDivOne {
public:
    double find(int n, int m) {
        vector<vector<double> > p(n+1, vector<double>(n));
        for (int t = 0; t < 300; t++) {
            p[1][0] = 1;
            for (int j = 2; j < n+1; j++) {
                p[j][0] = 1./6 + p[j][j-1]/2;
                for (int k = 1; k < n; k++) {
                    p[j][k] = p[j][k-1]/2 + p[j-1][k-1]/3;
                }
            }
        }
        return p[n][m-1];
    }
};