ABC314-E Roulettes

問題へのリンク

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("3 14");
            WillReturn.Add("100 2 5 9");
            WillReturn.Add("50 4 1 2 4 8");
            WillReturn.Add("70 5 2 4 2 8 8");
            //215.913355350494384765625
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2 100");
            WillReturn.Add("1 2 1 2");
            WillReturn.Add("10 6 0 0 0 0 0 100");
            //60
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("20 90");
            WillReturn.Add("3252 9 0 4 2 7 3 2 3 2 4");
            WillReturn.Add("2147 1 1");
            WillReturn.Add("4033 8 0 4 1 7 5 2 5 0");
            WillReturn.Add("3795 6 6 6 2 3 2 2");
            WillReturn.Add("3941 7 2 4 4 7 2 0 5");
            WillReturn.Add("2815 6 2 1 0 5 2 2");
            WillReturn.Add("3020 2 3 6");
            WillReturn.Add("3858 9 4 2 7 3 0 4 4 6 5");
            WillReturn.Add("4533 10 3 6 4 0 6 4 4 2 7 7");
            WillReturn.Add("4198 8 6 7 0 6 3 6 5 6");
            WillReturn.Add("3739 8 2 7 1 5 1 4 4 7");
            WillReturn.Add("2465 4 1 4 0 1");
            WillReturn.Add("4418 9 7 6 2 4 6 1 5 0 7");
            WillReturn.Add("5450 12 0 4 4 7 7 4 4 5 4 5 3 7");
            WillReturn.Add("4196 9 1 6 5 5 7 2 3 6 3");
            WillReturn.Add("4776 9 2 2 7 3 6 6 1 6 6");
            WillReturn.Add("2286 3 3 5 6");
            WillReturn.Add("3152 3 4 1 5");
            WillReturn.Add("3509 7 0 6 7 0 1 0 3");
            WillReturn.Add("2913 6 0 1 5 0 5 6");
            //45037.072314895291126319493887599716
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static decimal mM;

    struct RouletteInfoDef
    {
        internal decimal Cost;
        internal decimal[] PointArr;
    }
    static List<RouletteInfoDef> RouletteInfoList = new List<RouletteInfoDef>();

    static Dictionary<decimal, decimal> mAnswerDict = new Dictionary<decimal, decimal>();

    static void Main()
    {
        List<string> InputList = GetInputList();

        decimal[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(pX => decimal.Parse(pX)).ToArray();

        SplitAct(InputList[0]);
        mM = wkArr[1];

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            RouletteInfoDef WillAdd;
            WillAdd.Cost = wkArr[0];

            var PointList = new List<decimal>();
            for (int I = 2; I <= wkArr.GetUpperBound(0); I++) {
                PointList.Add(wkArr[I]);
            }
            WillAdd.PointArr = PointList.ToArray();
            RouletteInfoList.Add(WillAdd);
        }

        // 0点しかないルーレットはRemove
        for (int I = RouletteInfoList.Count - 1; 0 <= I; I--) {
            if (RouletteInfoList[I].PointArr.All(pX => pX == 0)) {
                RouletteInfoList.RemoveAt(I);
            }
        }

        // 後退解析
        for (decimal I = mM - 1; 0 <= I; I--) {
            decimal CurrEx = DeriveEx(I);
            mAnswerDict[I] = CurrEx;
        }
        Console.WriteLine(mAnswerDict[0]);
    }

    // 現在のポイントを引数として、残りコストの期待値を返す
    static decimal DeriveEx(decimal CurrPoint)
    {
        var KouhoList = new List<decimal>();

        foreach (RouletteInfoDef EachRouletteInfo in RouletteInfoList) {
            // 当たりの数
            decimal AtariCnt = EachRouletteInfo.PointArr.Count(pX => pX > 0);

            // 数値の数
            decimal NumCnt = EachRouletteInfo.PointArr.Length;

            decimal CurrEx = EachRouletteInfo.Cost;

            // 外れがある場合
            if (Array.Exists(EachRouletteInfo.PointArr, (pX => pX == 0))) {
                // 当たりの確率の逆数
                CurrEx = EachRouletteInfo.Cost * NumCnt / AtariCnt;
            }

            foreach (decimal EachPoint in EachRouletteInfo.PointArr) {
                if (EachPoint == 0) continue;

                decimal NextPoint = CurrPoint + EachPoint;
                if (NextPoint < mM) {
                    CurrEx += mAnswerDict[NextPoint] / AtariCnt; // 条件付き確率
                }
            }
            KouhoList.Add(CurrEx);
        }
        return KouhoList.Min();
    }
}

解説

後退解析で解いてます。