AtCoderのABC    次のABCの問題へ    前のABCの問題へ

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]);
    }
}


解説

簡単のため
金が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で解いてます。