IndeedなうE問題:Page Rank

行列計算じゃねとは思ったがそんなあっさり解けるとは思わなくて本番は手を付けなかった。

問題:http://indeednow-finala-open.contest.atcoder.jp/tasks/indeednow_2015_finala_e

解法:条件式を表す行列Aは転置行列が優対角行列になる。計算を反復するgauss-seidel法を用いれば収束するので1000回条件式を繰り返すと答えが求まる。
優対角行列を反復すると収束することは知ってたんですが転置行列が優対角行列のとき反復すると収束することは知らなかったので数値解析の教科書で調べてみたところ、反復式

は行列の固有値についての最大値が1未満なら収束するということでした。転置行列と元の行列は固有値が一致するので収束することが示せます。・・・よく考えれば当たり前でしたね。
以下ソースコード

const int MAXN = 10010;
double PR[2][MAXN];
vector<int> g[MAXN];

int main(void) {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        g[--a].push_back(--b);
    }
    int t = 0;
    for (int i = 0; i < n; i++) PR[t][i] = 1;
    for (int i = 0; i < 1000; i++) {
        for (int j = 0; j < n; j++) {
            PR[1-t][j] = 0.1;
        }
        for (int j = 0; j < n; j++) {
            for (int el : g[j]) {
                PR[1-t][el] += 0.9*PR[t][j]/g[j].size();
            }
        }
        t = 1-t;
    }
    for (int i = 0; i < n; i++) printf("%.10lf\n", PR[t][i]);
    return 0;
}