TopCoder SRM603: GraphWalkWithProbabilities

行動パターンとしては、初期位置からある位置 X に移動してから勝利するまでずっとそこに留まるのがベストになる。すでに X にいるとして 勝利するまで留まるときの勝率を E[X] とすると

\( E[X] = (winprob[X] + (100 - looseprob[X] - win[X]) E[X]) / 100 \)
これを移項して
\( E[X] = winprob[X] / (looseprob[X] + winprob[X]) \)

となる。終点での勝率はこれで求められるので、あとはそこから逆順に始点まで辿っていけば良い。ただし初期位置に無駄に待機しないように調整する必要があるので注意する。

以下のコードでは、PriorityQueue を使ったダイクストラで実装しているが、全点からスタートしているので、Warshall-Floyd を使ったほうがより簡単に実装できる。

public class GraphWalkWithProbabilities {
    struct Data {
        public int pos;
        public double win;
    }

    public double findprob(string[] graph, int[] winprob, int[] looseprob, int Start) {
        double ans = 0;
        int n = graph.Length;
        var pq = new PriorityQueue<Data>((d1, d2) => d1.win.CompareTo(d2.win));
        for (int i = 0; i < n; i++) {
            double X = 1.0 * winprob[i] / (looseprob[i] + winprob[i]);
            pq.Enqueue(new Data() { win = X, pos = i });
        }
        var visited = new bool[n];
        while (pq.Any()) {
            var now = pq.Dequeue();
            if (visited[now.pos]) continue;
            visited[now.pos] = true;
            if (now.pos == Start) {
                ans = Math.Max(ans, now.win);
                continue;
            }
            for (int j = 0; j < n; j++) {
                if (graph[j][now.pos] == '1' && !visited[j]) {
                    double win = (winprob[j] / 100.0 + (100 - looseprob[j] - winprob[j]) / 100.0 * now.win);
                    if (j == Start) {
                        win = now.win;
                    }
                    pq.Enqueue(new Data() { pos = j, win = win });
                }
            }
        }
        return ans;
    }
}