ABC266-E Throwing the Die

問題へのリンク

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");
            //3.5000000000
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2");
            //4.2500000000
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("10");
            //5.6502176688
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int N = int.Parse(InputList[0]);

        // 期待値[残りのサイコロを振る数] なDict
        var AnswerDict = new Dictionary<int, double>();

        AnswerDict[1] = 3.5;
        for (int I = 2; I <= N; I++) {
            double NextVal = AnswerDict[I - 1];

            double CurrEx = 0;
            for (int J = 1; J <= 6; J++) {
                CurrEx += Math.Max(NextVal, J) / 6D;
            }
            AnswerDict[I] = CurrEx;
        }
        Console.WriteLine(AnswerDict[N]);
    }
}

解説

後退解析で、最適戦略をシュミレーションして解いてます。