AOJ 2363 不揃いなサイコロ

■■■問題■■■

パチンコや競馬などの賭け事にお金を使いすぎて，借金まみれになったあなたは，
帝愛グループの地下監獄に収容されてしまった．
ここであなたは，借金を返すまで奴隷のように働かなくてはならない．

またこの監獄にはあなたと同じ境遇の人が多く収容されているので，いくつかの班に分けられている．
ある班では，サイコロを3つ転がしてお椀にいれて楽しむ習慣がある．
最近，そこの班長が大変な目にあったとかいう話を聞いたが，あなたに直接関係はない．

あなたの所属する班ではひとつのサイコロを振って楽しむ習慣がある．
ルールは，サイコロを振って目の大きな値を出せば勝ちという簡単なものである．
ただ特殊なこととしては，用いられるサイコロのある面が出る確率が，同様に確からしくないということである．

またサイコロも種類が多く，10面体のものから100面体のものとさまざまに用意されている．
さらに何も値の書かれていない面まである． 何の値も書かれていない面が出たときは，再度振りなおしをする．

このゲームを仕切っている班長から，あらかじめ振っても良いサイコロをいくつか提示されたのだが，
どれを使っても勝てる気がしない時がある．

そこで，与えられたサイコロの内，班長が使うサイコロで出る値の期待値より高いサイコロがあるのかどうか調べたい．
期待値が高いとは班長のサイコロより，0.0000001より大きい時を指す． 

■■■入力■■■

t
n1 m1
v1 r1
・・・
vm1 rm1
n2 m2
・・・
nt mt
v1 r1
・・・
vmt rmt
p q
v1 r1
・・・
vq rq

入力の形式に含まれる各変数の意味と制約は以下の通りである．

●t は与えられるサイコロの数 t (0 < t <=10)
●n は何面体であるのかを表す整数 (4 <= m <= 100)
●m は数値の振られている面の数 (0 < m <= n)
●vi は面に振られている数値 (0<= v <= 100)
●ri はその面が出る確率 (0 < r <= 1.0)
     ●r1 + r2 + ・・・ + rm <= 1.0は保証される．
     ●また ri は小数第10位まで与えられることがある．
●p は班長の使うサイコロが何面体であるかを表す整数
●q は班長の使うサイコロに数値の振られている面の数

■■■出力■■■

班長の使うサイコロよりも期待値の高いサイコロがあればYES，そうでなければNOを出力せよ． 

C#のソース

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

class Program
{
    static string InputPattern = "Input1";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("2");
            WillReturn.Add("4 2");
            WillReturn.Add("4 0.4000000");
            WillReturn.Add("3 0.5000000");
            WillReturn.Add("4 1");
            WillReturn.Add("5 0.3333333");
            WillReturn.Add("5 3");
            WillReturn.Add("5 0.7777777");
            WillReturn.Add("4 0.1111111");
            WillReturn.Add("2 0.0001111");
            //YES
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2");
            WillReturn.Add("4 2");
            WillReturn.Add("4 0.5000000");
            WillReturn.Add("3 0.4000000");
            WillReturn.Add("4 1");
            WillReturn.Add("5 0.3333333");
            WillReturn.Add("5 3");
            WillReturn.Add("8 0.7777777");
            WillReturn.Add("4 0.1111111");
            WillReturn.Add("2 0.0001111");
            //NO
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

        var DiceDictList = new List<Dictionary<decimal, decimal>>();

        int CurrY = 1;

        decimal[] wkArr = { };
        Action SplitAct = () =>
            wkArr = InputList[CurrY].Split(' ').Select(X => decimal.Parse(X)).ToArray();

        while (CurrY <= InputList.Count - 1) {
            SplitAct();
            decimal MenCnt = wkArr[1];

            var WillAddDict = new Dictionary<decimal, decimal>();
            for (int I = 1; I <= MenCnt; I++) {
                CurrY++;
                SplitAct();
                if (WillAddDict.ContainsKey(wkArr[0])) {
                    WillAddDict[wkArr[0]] += wkArr[1];
                }
                else WillAddDict.Add(wkArr[0], wkArr[1]);
            }
            DiceDictList.Add(WillAddDict);
            CurrY++;
        }

        DebugDiceInfoPrint(DiceDictList);

        //班長のダイス
        Dictionary<decimal, decimal> HantyouDiceDict = DiceDictList.Last();

        //カイジのダイスのList
        DiceDictList.RemoveAt(DiceDictList.Count - 1);
        var KaijiDiceDictList = DiceDictList;

        decimal KaijiKitaiti = KaijiDiceDictList.Max(X => DeriveDiceKitaiti(X));
        decimal HantyouKitaiti = DeriveDiceKitaiti(HantyouDiceDict);
        Console.WriteLine(KaijiKitaiti > HantyouKitaiti ? "YES" : "NO");
    }

    //デバッグ用でダイス情報を表示
    static void DebugDiceInfoPrint(List<Dictionary<decimal, decimal>> pDiceDictList)
    {
        for (int I = 0; I <= pDiceDictList.Count - 1; I++) {
            Console.WriteLine(new string('■', 20));
            Console.WriteLine("{0}個目のダイス情報", I + 1);
            foreach (var EachPair in pDiceDictList[I]) {
                Console.WriteLine("{0}が出る確率が{1}",
                    EachPair.Key, EachPair.Value);
            }
            Console.WriteLine("期待値={0}", DeriveDiceKitaiti(pDiceDictList[I]));
        }
    }

    //ダイスの期待値を求める
    static decimal DeriveDiceKitaiti(Dictionary<decimal, decimal> pDiceDict)
    {
        decimal WillReturn = 0;
        decimal BunboSum = pDiceDict.Values.Sum();
        foreach (var EachPair in pDiceDict) {
            WillReturn += EachPair.Key * EachPair.Value / BunboSum;
        }
        return WillReturn;
    }
}

デバッグ情報付の実行結果

■■■■■■■■■■■■■■■■■■■■
1個目のダイス情報
4が出る確率が0.4000000
3が出る確率が0.5000000
期待値=3.4444444444444444444444444445
■■■■■■■■■■■■■■■■■■■■
2個目のダイス情報
5が出る確率が0.3333333
期待値=5
■■■■■■■■■■■■■■■■■■■■
3個目のダイス情報
5が出る確率が0.7777777
4が出る確率が0.1111111
2が出る確率が0.0001111
期待値=4.8746407058088532968338916574
YES

解説

ダイスごとの期待値を集計して、解を求めてます。