using System; using System.Collections.Generic; using System.Linq; class Program { static string InputPattern = "Input4"; static List GetInputList() { var WillReturn = new List(); 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 InputList = GetInputList(); int N = int.Parse(InputList[0]); int[] AArr = InputList[1].Split(' ').Select(X => int.Parse(X)).ToArray(); var DPInfoList = new List(); Action 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)); } }