TDP J ボール

問題へのリンク

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");
            WillReturn.Add("0 2");
            //4.500000000
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5");
            WillReturn.Add("1 3 4 2 5");
            //8.986111111
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] XArr = InputList[1].Split(' ').Select(pX => int.Parse(pX)).ToArray();

        int UB = XArr.Max();
        char[] BanArr = new char[UB + 1];

        for (int I = 0; I <= UB; I++) {
            BanArr[I] = '1';
        }
        foreach (int EachInt in XArr) {
            BanArr[EachInt] = '0';
        }

        string BanStr = new string(BanArr);
        double Answer = dfs(BanStr);
        Console.WriteLine(Answer);
    }

    // 再帰
    static double dfs(string pBan)
    {
        int UB = pBan.Length - 1;

        // 1番左の0を求める
        int Target = pBan.IndexOf('0');
        if (Target == -1) return 0D;

        // 1つ右がUB以下なら、ここに投げる
        if (Target + 1 <= UB) {
            Target++;
        }

        List<int> ZeroIndList = DeriveZeroIndList(pBan, Target);
        var KouhoList = new List<double>();

        char[] BanArr = pBan.ToCharArray();

        // 1の場合は、コンプガチャ問題の期待値
        if (ZeroIndList.Count == 1) {
            return 3 + dfs(UpdateOne(pBan, ZeroIndList[0]));
        }
        else if (ZeroIndList.Count == 2) {
            // 自己ループ以外になる確率
            double NonLoopProb = 2D / 3D;

            double NewEx = 1D / NonLoopProb; // 自己ループ以外になる確率の逆数

            KouhoList.Add(1D / 2D * dfs(UpdateOne(pBan, ZeroIndList[0])));
            KouhoList.Add(1D / 2D * dfs(UpdateOne(pBan, ZeroIndList[1])));

            // 自己ループ以外の条件付確率 * 期待値を集計
            NewEx += KouhoList.Sum();

            return NewEx;
        }
        KouhoList.Add(1D / 3D * dfs(UpdateOne(pBan, ZeroIndList[0])));
        KouhoList.Add(1D / 3D * dfs(UpdateOne(pBan, ZeroIndList[1])));
        KouhoList.Add(1D / 3D * dfs(UpdateOne(pBan, ZeroIndList[2])));
        return 1 + KouhoList.Sum();
    }

    // 盤面と指定座標を引数として、左右も含めた0の座標のListを返す
    static List<int> DeriveZeroIndList(string pBan, int pBaseInd)
    {
        int UB = pBan.Length - 1;

        var WillReturn = new List<int>();

        if (pBaseInd - 1 >= 0) {
            if (pBan[pBaseInd - 1] == '0') {
                WillReturn.Add(pBaseInd - 1);
            }
        }

        if (pBan[pBaseInd] == '0') {
            WillReturn.Add(pBaseInd);
        }

        if (pBaseInd + 1 <= UB) {
            if (pBan[pBaseInd + 1] == '0') {
                WillReturn.Add(pBaseInd + 1);
            }
        }
        return WillReturn;
    }

    // string型の引数のIndを1にUpdateする
    static string UpdateOne(string pStr, int pInd)
    {
        char[] CharArr = pStr.ToCharArray();
        CharArr[pInd] = '1';
        return new string(CharArr);
    }
}

解説

期待値DPでなく、再帰で解いてます。

類題

第5回PAST K 的あて