結果

問題 No.108 トリプルカードコンプ
ユーザー 明智重蔵
提出日時 2015-09-12 14:27:48
言語 C#(csc)
(csc 3.9.0)
結果
TLE  
実行時間 -
コード長 4,601 bytes
コンパイル時間 988 ms
コンパイル使用メモリ 110,208 KB
実行使用メモリ 30,336 KB
最終ジャッジ日時 2024-07-19 06:17:29
合計ジャッジ時間 7,815 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 4 TLE * 1 -- * 15
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "Input4";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("1");
            WillReturn.Add("0");
            //3
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2");
            WillReturn.Add("1 2");
            //4.5
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("8");
            WillReturn.Add("3 4 5 6 7 8 9 10");
            //0
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    //確率の下限
    const decimal KakurituKagen = 0.0000000000000000000000001M;

    //DP表の構造体
    struct DPInfoDef
    {
        internal int CardCnt; //カードの総枚数
        internal int Cnt0; //0種類持つカードの数
        internal int Cnt1; //1種類持つカードの数
        internal int Cnt2; //2種類持つカードの数
        internal int Cnt3; //3種類持つカードの数
        internal decimal Kakuritu; //状態遷移する確率
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int N = int.Parse(InputList[0]);
        int[] AArr = InputList[1].Split(' ').Select(X => int.Parse(X)).ToArray();
        var DPInfoList = new List<DPInfoDef>();

        Action<DPInfoDef> MergeAct = (pDPInfo) =>
        {
            //{CardCnt,Cnt0,Cnt1,Cnt2,Cnt3}をキーとして、確率の加法定理を使う
            int wkInd = DPInfoList.FindIndex(X => X.CardCnt == pDPInfo.CardCnt
                                               && X.Cnt0 == pDPInfo.Cnt0
                                               && X.Cnt1 == pDPInfo.Cnt1
                                               && X.Cnt2 == pDPInfo.Cnt2
                                               && X.Cnt3 == pDPInfo.Cnt3);
            if (wkInd >= 0) {
                pDPInfo.Kakuritu += DPInfoList[wkInd].Kakuritu;
                DPInfoList.RemoveAt(wkInd);
            }

            DPInfoList.Add(pDPInfo);
        };

        //初期化
        DPInfoDef WillMerge;
        WillMerge.CardCnt = 0;
        WillMerge.Cnt1 = AArr.Count(X => X == 1);
        WillMerge.Cnt2 = AArr.Count(X => X == 2);
        WillMerge.Cnt3 = AArr.Count(X => X >= 3);
        WillMerge.Cnt0 = N - WillMerge.Cnt1 - WillMerge.Cnt2 - WillMerge.Cnt3;
        WillMerge.Kakuritu = 1M;
        MergeAct(WillMerge);

        for (int I = 0; I <= DPInfoList.Count - 1; I++) {
            if (DPInfoList[I].Cnt3 == N) continue;

            //0種類持つカードを引く場合
            if (DPInfoList[I].Cnt0 > 0) {
                WillMerge = DPInfoList[I];
                WillMerge.Kakuritu *= (decimal)WillMerge.Cnt0 / N;
                WillMerge.CardCnt++;
                WillMerge.Cnt0--;
                WillMerge.Cnt1++;
                if (WillMerge.Kakuritu > KakurituKagen)
                    MergeAct(WillMerge);
            }

            //1種類持つカードを引く場合
            if (DPInfoList[I].Cnt1 > 0) {
                WillMerge = DPInfoList[I];
                WillMerge.Kakuritu *= (decimal)WillMerge.Cnt1 / N;
                WillMerge.CardCnt++;
                WillMerge.Cnt1--;
                WillMerge.Cnt2++;
                if (WillMerge.Kakuritu > KakurituKagen)
                    MergeAct(WillMerge);
            }

            //2種類持つカードを引く場合
            if (DPInfoList[I].Cnt2 > 0) {
                WillMerge = DPInfoList[I];
                WillMerge.Kakuritu *= (decimal)WillMerge.Cnt2 / N;
                WillMerge.CardCnt++;
                WillMerge.Cnt2--;
                WillMerge.Cnt3++;
                if (WillMerge.Kakuritu > KakurituKagen)
                    MergeAct(WillMerge);
            }

            //3種類持つカードを引く場合
            if (DPInfoList[I].Cnt3 > 0) {
                WillMerge = DPInfoList[I];
                WillMerge.Kakuritu *= (decimal)WillMerge.Cnt3 / N;
                WillMerge.CardCnt++;
                if (WillMerge.Kakuritu > KakurituKagen)
                    MergeAct(WillMerge);
            }
        }
        DPInfoList.RemoveAll(X => X.Cnt3 < N);
        //Console.WriteLine("確率の総和={0}", DPInfoList.Sum(X => X.Kakuritu));
        Console.WriteLine(DPInfoList.Sum(X => X.CardCnt * X.Kakuritu));
    }
}
0