ABC193-D Poker

問題へのリンク

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("1144#");
            WillReturn.Add("2233#");
            //0.4444444444444444
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2");
            WillReturn.Add("9988#");
            WillReturn.Add("1122#");
            //1.0
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("6");
            WillReturn.Add("1122#");
            WillReturn.Add("2228#");
            //0.001932367149758454
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("100000");
            WillReturn.Add("3226#");
            WillReturn.Add("3597#");
            //0.6296297942426154
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

        int K = int.Parse(InputList[0]);
        string S = InputList[1];
        string T = InputList[2];

        var AppearCntDict = new Dictionary<int, int>();
        foreach (var EachPair in S.ToCharArray().GroupBy(pX => pX)) {
            AppearCntDict[EachPair.Key - '0'] = EachPair.Count();
        }
        foreach (var EachPair in T.ToCharArray().GroupBy(pX => pX)) {
            if (AppearCntDict.ContainsKey(EachPair.Key - '0') == false) {
                AppearCntDict[EachPair.Key - '0'] = 0;
            }
            AppearCntDict[EachPair.Key - '0'] += EachPair.Count();
        }

        decimal Answer = 0M;
        for (int I = 1; I <= 9; I++) {
            for (int J = 1; J <= 9; J++) {
                // 高橋君の得点
                string StrTakahashi = S.Replace("#", I.ToString());
                decimal ScoreTakahashi = DeriveScore(StrTakahashi);

                // 青木君の得点
                string StrAoki = T.Replace("#", J.ToString());
                decimal ScoreAoki = DeriveScore(StrAoki);

                if (ScoreTakahashi <= ScoreAoki) continue;
                //Console.WriteLine("高橋君={0},青木君={1}", StrTakahashi, StrAoki);

                decimal Prob = DeriveProb(K, AppearCntDict, I, J);
                Answer += Prob;
            }
        }
        Console.WriteLine(Answer);
    }

    // 高橋君がAを引いて、青木君がBを引く確率を返す
    static decimal DeriveProb(int pK, Dictionary<int, int> pAppearCntDict, int pA, int pB)
    {
        decimal Prob = 0M;

        int AppearACnt = 0;
        if (pAppearCntDict.ContainsKey(pA)) {
            AppearACnt = pAppearCntDict[pA];
        }
        Prob = (decimal)(pK - AppearACnt) / (decimal)(pK * 9 - 8);

        int AppearBCnt = 0;
        if (pAppearCntDict.ContainsKey(pB)) {
            AppearBCnt = pAppearCntDict[pB];
        }
        if (pA == pB) AppearBCnt++;

        Prob *= (decimal)(pK - AppearBCnt) / (decimal)(pK * 9 - 9);
        return Prob;
    }

    // 文字列を引数として、得点を返す
    static decimal DeriveScore(string pStr)
    {
        decimal WillReturn = 0M;
        for (int I = 1; I <= 9; I++) {
            int ApeearCnt = pStr.ToCharArray().Count((pX => (pX - '0') == I));
            WillReturn += I * (decimal)(Math.Pow(10, ApeearCnt));
        }
        return WillReturn;
    }
}

解説

高橋君と青木君が引く数字の組み合わせは、
9*9で81通りしかないので全探索して、確率の加法定理を使ってます。