TDP C トーナメント

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("1");
            WillReturn.Add("2200");
            WillReturn.Add("2600");
            //0.090909091
            //0.909090909
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3");
            WillReturn.Add("2000");
            WillReturn.Add("2500");
            WillReturn.Add("2300");
            WillReturn.Add("2700");
            WillReturn.Add("2100");
            WillReturn.Add("2400");
            WillReturn.Add("2600");
            WillReturn.Add("2200");
            //0.000086893
            //0.122042976
            //0.005522752
            //0.493464665
            //0.000651695
            //0.053982389
            //0.321828438
            //0.002420190
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static Dictionary<int, List<HashSet<int>>> mDivSetListDict = new Dictionary<int, List<HashSet<int>>>();

    static void Main()
    {
        int[] NumArr = Enumerable.Range(0, 1024).ToArray();

        mDivSetListDict[1] = DeriveDivSetList(NumArr, 2);
        mDivSetListDict[2] = DeriveDivSetList(NumArr, 4);
        mDivSetListDict[3] = DeriveDivSetList(NumArr, 8);
        mDivSetListDict[4] = DeriveDivSetList(NumArr, 16);
        mDivSetListDict[5] = DeriveDivSetList(NumArr, 32);
        mDivSetListDict[6] = DeriveDivSetList(NumArr, 64);
        mDivSetListDict[7] = DeriveDivSetList(NumArr, 128);
        mDivSetListDict[8] = DeriveDivSetList(NumArr, 256);
        mDivSetListDict[9] = DeriveDivSetList(NumArr, 512);
        mDivSetListDict[10] = DeriveDivSetList(NumArr, 1024);

        List<string> InputList = GetInputList();
        double[] RArr = InputList.Skip(1).Select(pX => double.Parse(pX)).ToArray();

        // 確率 [人 , 連勝数] なDP表
        int UB_I = RArr.GetUpperBound(0);
        int UB_J = DeriveMaxWinCnt(RArr.Length);

        double[,] DPArr = new double[UB_I + 1, UB_J + 1];
        for (int I = 0; I <= UB_I; I++) {
            DPArr[I, 0] = 1D;
        }

        for (int J = 1; J <= UB_J; J++) {
            for (int I = 0; I <= UB_I; I++) {
                HashSet<int> TaisenKouhoSet = DeriveTaisenKouhoSet(I, J);

                // 確率の乗法定理と加法定理
                double ProbSum = 0;
                foreach (int EachI in TaisenKouhoSet) {
                    double CurrProb = 0;
                    CurrProb = DPArr[EachI, J - 1];
                    CurrProb *= DeriveWinProb(RArr[I], RArr[EachI]);
                    ProbSum += CurrProb;
                }
                DPArr[I, J] = DPArr[I, J - 1] * ProbSum;
            }
        }

        for (int I = 0; I <= UB_I; I++) {
            decimal wkDec = Convert.ToDecimal(DPArr[I, UB_J]);
            Console.WriteLine(wkDec);
        }
    }

    // 人と何試合目かを引数として、対戦候補のHashSetを返す
    static HashSet<int> DeriveTaisenKouhoSet(int pHito, int pGameNo)
    {
        HashSet<int> AnswerSet = new HashSet<int>();
        AnswerSet.UnionWith(mDivSetListDict[pGameNo].First(pX => pX.Contains(pHito)));
        AnswerSet.Remove(pHito);
        for (int I = 1; I <= pGameNo - 1; I++) {
            HashSet<int> ExceptSet = mDivSetListDict[I].First(pX => pX.Contains(pHito));
            AnswerSet.ExceptWith(ExceptSet);
        }
        return AnswerSet;
    }

    // 配列を指定の数で分割した、SetのListを返す
    static List<HashSet<int>> DeriveDivSetList(int[] pArr, int pDivCnt)
    {
        var WillReturn = new List<HashSet<int>>();

        var DivSet = new HashSet<int>();
        for (int I = 0; I <= pArr.GetUpperBound(0); I++) {
            DivSet.Add(pArr[I]);
            if (DivSet.Count == pDivCnt) {
                WillReturn.Add(new HashSet<int>(DivSet));
                DivSet.Clear();
            }
        }
        return WillReturn;
    }

    // 人数から優勝に必要な連勝数を求める
    static int DeriveMaxWinCnt(int pCnt)
    {
        int WillReturn = 0;
        while (pCnt > 1) {
            pCnt /= 2;
            WillReturn++;
        }
        return WillReturn;
    }

    // PとQのレーティングを引数として、Pが勝つ確率を返す
    static double DeriveWinProb(double pP, double pQ)
    {
        return 1 / (1 + Math.Pow(10, (pQ - pP) / 400));
    }
}

解説

確率 [人 , 連勝数] なDP表を
確率の乗法定理と加法定理で更新してます。