ABC382-E Expansion Packs

問題へのリンク

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("2 2");
            WillReturn.Add("50 100");
            //1.5000000000000000
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2 3");
            WillReturn.Add("40 60");
            //3.2475579530543811
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("6 3");
            WillReturn.Add("10 33 33 10 100 10");
            //1.8657859189536100
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

    static long mX;
    static long[] mPArr;

    // 枚数[確率]な確率分布のDict
    static Dictionary<long, double> mProbDict = new Dictionary<long, double>();

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = GetSplitArr(InputList[0]);
        mX = wkArr[1];

        mPArr = GetSplitArr(InputList[1]);

        DeriveProbDict();

        double Answer = rec(0);
        Console.WriteLine(Answer);
    }

    // 確率DPで、1セットの確率分布を求める
    static void DeriveProbDict()
    {
        var PrevDict = new Dictionary<long, double>();
        PrevDict[0] = 1D;
        foreach (long EachP in mPArr) {
            var CurrDict = new Dictionary<long, double>();
            foreach (var EachPair in PrevDict) {

                Action<long, double> AddAct = (pTargetKey, pAddVal) =>
                {
                    if (CurrDict.ContainsKey(pTargetKey) == false) {
                        CurrDict[pTargetKey] = 0;
                    }
                    CurrDict[pTargetKey] += pAddVal;
                };

                double CurrP = EachP;
                CurrP /= 100D;
                double RevP = 1 - CurrP;

                // アタリの場合
                AddAct(EachPair.Key + 1, EachPair.Value * CurrP);

                // ハズレの場合
                AddAct(EachPair.Key, EachPair.Value * RevP);
            }
            PrevDict = CurrDict;
        }
        mProbDict = PrevDict;
    }

    // 現在マスを引数とし、ゴールより右に移動するまでのサイコロを振る期待値を返す
    static Dictionary<long, double> mMemo = new Dictionary<long, double>();
    static double rec(long pCurrPos)
    {
        if (mMemo.ContainsKey(pCurrPos)) {
            return mMemo[pCurrPos];
        }

        if (pCurrPos >= mX) return 0D;

        var SeniList = new List<double>();

        if (mProbDict.ContainsKey(0)) {
            // 移動0がある場合
            double ProbSum = mProbDict.Where(pX => pX.Key > 0).Sum(pX => pX.Value);
            double Rev = 1 / ProbSum;

            foreach (var EachPair in mProbDict) {
                if (EachPair.Key == 0) continue;
                SeniList.Add((Rev + rec(pCurrPos + EachPair.Key)) * EachPair.Value / ProbSum);
            }
        }
        else {
            // 移動0がない場合
            foreach (var EachPair in mProbDict) {
                SeniList.Add((1 + rec(pCurrPos + EachPair.Key)) * EachPair.Value);
            }
        }
        return mMemo[pCurrPos] = SeniList.Sum();
    }
}

解説

まず、確率DPを行い、
1パックを空けた時の
確率分布を作成します。

そして、この確率分布を、
サイコロを1回振った時に
進めるマス[確率]
として、双六でスタートからゴールに進むまでに
サイコロを振る回数の期待値を求める問題に帰着して解いてます。