ABC184-D increment of coins

問題へのリンク

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("99 99 99");
            //1.000000000
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("98 99 99");
            //1.331081081
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("0 0 1");
            //99.000000000
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("31 41 59");
            //91.835008202
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

        int[] wkArr = InputList[0].Split(' ').Select(pX => int.Parse(pX)).ToArray();
        int A = wkArr[0];
        int B = wkArr[1];
        int C = wkArr[2];

        int UB = 100;

        // 試行回数の期待値[Aの枚数,Bの枚数,Cの枚数] なDP表
        decimal[, ,] DPArr = new decimal[UB + 1, UB + 1, UB + 1];

        for (int LoopA = UB - 1; A <= LoopA; LoopA--) {
            for (int LoopB = UB - 1; B <= LoopB; LoopB--) {
                for (int LoopC = UB - 1; C <= LoopC; LoopC--) {
                    // 貰うDP
                    decimal Bunbo = LoopA + LoopB + LoopC;
                    decimal Moto1 = DPArr[LoopA + 1, LoopB, LoopC] * LoopA / Bunbo;
                    decimal Moto2 = DPArr[LoopA, LoopB + 1, LoopC] * LoopB / Bunbo;
                    decimal Moto3 = DPArr[LoopA, LoopB, LoopC + 1] * LoopC / Bunbo;

                    DPArr[LoopA, LoopB, LoopC] = 1 + Moto1 + Moto2 + Moto3;
                }
            }
        }
        Console.WriteLine(DPArr[A, B, C]);
    }
}

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("99 99 99");
            //1.000000000
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("98 99 99");
            //1.331081081
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("0 0 1");
            //99.000000000
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("31 41 59");
            //91.835008202
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = InputList[0].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        long A = wkArr[0];
        long B = wkArr[1];
        long C = wkArr[2];

        double Result = DFS(A, B, C);
        Console.WriteLine(Result);
    }

    static Dictionary<long, double> mMemo = new Dictionary<long, double>();
    static double DFS(long pA, long pB, long pC)
    {
        if (pA == 100) return 0;
        if (pB == 100) return 0;
        if (pC == 100) return 0;

        long Hash = pA * 1000000 + pB * 1000 + pC;
        if (mMemo.ContainsKey(Hash)) {
            return mMemo[Hash];
        }

        // 分母を求める
        double Bunbo = pA + pB + pC;
        double Ex1 = DFS(pA + 1, pB, pC) * pA / Bunbo;
        double Ex2 = DFS(pA, pB + 1, pC) * pB / Bunbo;
        double Ex3 = DFS(pA, pB, pC + 1) * pC / Bunbo;

        return mMemo[Hash] = 1 + Ex1 + Ex2 + Ex3;
    }
}

解説

簡単のため
金が1枚、銀が1枚の状態からスタートし
金か銀の少なくとも片方が3枚になるまで試行する時の
試行回数の期待値を考えます。

すると、横軸を銀の枚数、縦軸を金の枚数として
下記のような2次元表となります。

  0 1 2 3
0 / / / /
1 / ? ? 0
2 / ? ? 0
3 / 0 0 /

[2,2]は1と分かるので埋めます。

  0 1 2 3
0 / / / /
1 / ? ? 0
2 / ? 1 0
3 / 0 0 /

[1,2]は、
[2,2]に1/3の確率で遷移し
[1,3]に2/3の確率で遷移するので、

遷移確率と遷移後の期待値により、
[1,2] = [2,2] * 1/3
      + [1,3] * 2/3
      + 1
で
[1,2] = 4/3 と分かります。
対称性により
[2,1] も 4/3になり。

[1,1] = [1,2] * 1/2
      + [2,1] * 1/2
      + 1
= 7/3
になります。

以上により漸化式が分かったので、貰うDPで解いてます。

メモ化再帰で解くこともできます。