Educational DP Contest J Sushi

問題へのリンク

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");
            WillReturn.Add("1 1 1");
            //5.5
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("1");
            WillReturn.Add("3");
            //3
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("2");
            WillReturn.Add("1 2");
            //4.5
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("10");
            WillReturn.Add("1 3 2 3 3 2 3 2 1 3");
            //54.48064457488221
        }
        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]);
        int[] AArr = InputList[1].Split(' ').Select(pX => int.Parse(pX)).ToArray();
        int UB = N;

        int Cnt1 = AArr.Where(pX => pX == 1).Count();
        int Cnt2 = AArr.Where(pX => pX == 2).Count();
        int Cnt3 = AArr.Where(pX => pX == 3).Count();

        // 試行回数の期待値[1個ある寿司の数,2個ある寿司の数,3個ある寿司の数] なDP表
        double[, ,] DPArr = new double[UB + 1, UB + 1, UB + 1];

        for (int K = 0; K <= UB; K++) {
            for (int J = 0; J <= UB; J++) {
                for (int I = 0; I <= UB; I++) {
                    if (I == 0 && J == 0 && K == 0) continue;
                    if (K + I + J > N) break;

                    // 貰うDP
                    double BunshiSum = 0;
                    double BunboSum = 0;
                    if (I > 0) {
                        BunshiSum += DPArr[I - 1, J, K] * I;
                        BunboSum += I;
                    }
                    if (J > 0) {
                        BunshiSum += DPArr[I + 1, J - 1, K] * J;
                        BunboSum += J;
                    }
                    if (K > 0) {
                        BunshiSum += DPArr[I, J + 1, K - 1] * K;
                        BunboSum += K;
                    }
                    // 自己ループ以外になる確率
                    double NonLoopProb = BunboSum / N;

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

                    // 自己ループ以外の条件付確率 * 期待値を集計
                    NewEx += BunshiSum / BunboSum;
                    DPArr[I, J, K] = NewEx;
                }
            }
        }
        Console.WriteLine(DPArr[Cnt1, Cnt2, Cnt3]);
    }
}

解説

貰うDPで
遷移確率と、遷移先の期待値から求めた期待値を埋めていってます。

各遷移で、自己ループがあるので、
自己ループ以外に遷移する確率の逆数を期待値に計上しつつ、
条件付確率で、各遷移確率を求めてます。