TCHS09 Elimination Round 2 Medium

問題

8人でトーナメント形式の大会を行う。ある人が他のある人に勝利する確率が与えられるので、8人それぞれが優勝する確率を求めなさい。

解

n人目が決勝に出る確率 r[n] は、i人目がj人目に勝てる確率を p[i, j] とすると

b = {2, 0, 6, 4}[n / 2]

r[n] = p[n, n ^ 1] * (p[b, b + 1] * p[n, b] + p[b + 1, b] * p[n, b + 1])

である。(x^y は x XOR y)

また、n人目が優勝する確率 R[n] は

b = (1 - n / 4) * 4

R[n] = r[n] * (p[b, b + 1] * p[n, b] + p[b + 1, b] * p[n, b + 1] + p[b + 2, b + 3] * p[n, b + 2] + p[b + 3, b + 2] * p[b, b + 3])

となる。

using System;
using System.Text;
using System.Text.RegularExpressions;
using System.Collections;
using System.Collections.Generic;

public class TournamentWinner {
    double[,] pr;
    public double[] winningProbabilities(int[] P) {
        pr = new double[8, 8];
        int[] k = new int[] {0, 7, 13, 18, 22, 25, 27};
        int pi = 0;
        for (int i = 0; i < 8; ++i)
            for (int j = i + 1; j < 8; ++j)
                pr[j, i] = 1 - (pr[i, j] = P[pi++] / 100.0);
        double[] r1 = new double[8];
        for(int i = 0; i < 8; ++i)
        {
            int b = new int[] { 2, 0, 6, 4 }[i / 2];
            r1[i] = pr[i, i ^ 1] * (pr[b, b + 1] * pr[i, b] + pr[b + 1, b] * pr[i, b + 1]);
        }

        double[] r2 = new double[8];
        for (int i = 0; i < 8; ++i)
        {
            int b = (1 - i / 4) * 4;
            r2[i] = r1[i];
            double tmp = 0.0;
            for (int j = 0; j < 4; ++j)
                tmp += r1[b + j] * pr[i, b + j];
            r2[i] *= tmp;
        }
        return r2;
    }
}