AT_arc016_3 [ARC016C] ソーシャルゲーム

[problemUrl]: https://atcoder.jp/contests/arc016/tasks/arc016_3 高橋君は、アイドルを集めるカードゲームが大好きです。 このゲームでは、お金を払ってくじを引くことにより、ある確率分布によって決定されるアイドルが $ 1 $ 人、手に入ります。 高橋君は、すべてのアイドルを集めたいです。 くじは $ M $ 種類あり、それぞれのくじで、各アイドルの出現確率や、$ 1 $ 回くじをひくために必要な金額が違います。 高橋君がすべてのアイドルを集めるために最適な戦略を取った場合、必要な金額の期待値を求めなさい。 入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ C_1 $ $ cost_1 $ $ idol_{1,1} $ $ p_{1,1} $ $ idol_{1,2} $ $ p_{1,2} $ : $ idol_{1,C_1} $ $ p_{1,C_1} $ : $ C_M $ $ cost_M $ $ idol_{M,1} $ $ p_{M,1} $ $ idol_{M,2} $ $ p_{M,2} $ : $ idol_{M,C_M} $ $ p_{M,C_M} $ 1. $ 1 $ 行目に、アイドルの総数を表す整数 $ N(1≦N≦10) $、くじの種類を表す整数 $ M(1≦M≦4) $が半角空白区切りで与えられる。 2. $ 2 $ 行目以降で $ i(1≦i≦M) $ 回、くじに関する情報が半角空白区切りで与えられる。 - 整数 $ C_i\ (1≦C_i≦N) $ は、$ i $ 番目のくじに含まれるアイドルの枚数を表す。 - 整数 $ cost_i\ (1≦cost_i≦3000) $ は、$ i $ 番目のくじをひくのにかかる値段を表す。 5. $ C_i $ と $ cost_i $ 以降で、$ i $ 番目のくじに含まれるアイドルの情報が $ j(1≦j≦C_i) $ 回与えられる。 - 整数 $ idol_{i,j}\ (1≦idol_{i,j}≦N) $ は、$ i $ 番目のくじに含まれる $ j $ 番目のアイドルである。 - 整数 $ p_{i,j}\ (1≦p_{i,j}≦100) $ は、$ i $ 番目のくじに含まれる $ j $ 番目のアイドルの、百分率表記での出現確率を表す。 - $ i $ 番目のくじに含まれるすべてのアイドルの出現率を足すと、$ 100 $ になる。 高橋君がすべてのアイドルを集めるために最適な戦略を取った場合、必要な金額の期待値を求めなさい。 出力は絶対誤差あるいは相対誤差の少なくとも片方が $ 10^{-6} $ 以下であれば許容される。 なお、出力の最後には改行をいれること。 この問題は、非常に多くの部分点が設定されています。満点が取れる解法が解らない場合も、部分点だけを狙ったコードを提出してみましょう。 また、D問題の難易度も同程度となっております。両方の問題を読んでみることをお勧めします。 ```

5 2
2 300
3 5
4 95
3 500
5 20
1 30
2 50
```

 ```
9343.17042606516
```

- アイドルは $ 5 $ 種類、くじは $ 2 $ 種類です。

1. $ 1 $ 番目のくじでは $ 2 $ 種類のアイドルを獲得することができ、$ 1 $ 回ごとに費用が $ 300 $ だけかかります。

- $ 1 $ 番目のくじに含まれる $ 1 $ 番目のアイドルは、アイドル $ 3 $ で、出現確率は $ 5% $ です。
- $ 1 $ 番目のくじに含まれる $ 2 $ 番目のアイドルは、アイドル $ 4 $ で、出現確率は $ 95% $ です。

17. $ 2 $ 番目のくじでは $ 3 $ 種類のアイドルを獲得することができ、$ 1 $ 回ごとに費用が $ 500 $ だけかかります。
- $ 2 $ 番目のくじに含まれる $ 1 $ 番目のアイドルは、アイドル $ 5 $ で、出現確率は $ 20% $ です。
- $ 2 $ 番目のくじに含まれる $ 2 $ 番目のアイドルは、アイドル $ 1 $ で、出現確率は $ 30% $ です。
- $ 2 $ 番目のくじに含まれる $ 3 $ 番目のアイドルは、アイドル $ 2 $ で、出現確率は $ 50% $ です。

19. この入力では、$ 2 $ つのくじで手に入るアイドルが全て違います。
20. $ 1 $ つめのくじでかかる金額が $ 6015.789473684 $ 、$ 2 $ つめのくじでかかる金額が $ 3327.380952381 $ なので、合わせて $ 9343.17042606516 $ が答えとなります。
 ```
3 3
1 10
1 100
1 10
2 100
1 10
3 100
```

 ```
30
```

- $ 1 $ 番目のくじ、$ 2 $ 番目のくじ、$ 3 $ 番目のくじをそれぞれ $ 1 $ 回ずつひくと、アイドルをすべて集めることができます。
 
```
1 1
1 1000
1 100
```

 ```
1000
```

- アイドルもくじも $ 1 $つずつしかないので、くじを $ 1 $ 回引くだけで良いです。
 
```
2 2
2 1000
1 30
2 70
2 800
1 80
2 20
```

 ```
2128.57142857143
```

 ```
3 3
2 50
1 99
2 1
3 300
1 90
2 9
3 1
3 3000
1 80
2 15
3 5
```

 ```
30333.4291970656
```
                            

N/A

N/A