C - ソーシャルゲーム Editorial /

Time Limit: 2 sec / Memory Limit: 64 MB

問題文

高橋君は、アイドルを集めるカードゲームが大好きです。
このゲームでは、お金を払ってくじを引くことにより、ある確率分布によって決定されるアイドルが 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 番目のくじをひくのにかかる値段を表す。
  3. 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 になる。

部分点

    この問題には部分点が設定されている。
  • N=1 かつ M=1 を満たす全ての入力に正解した場合、10 点。
  • N=1 を満たす全ての入力に正解した場合、さらに 10 点。
  • C_i=1 を満たす全ての入力に正解した場合、さらに 10 点。
  • N≦2 を満たす全ての入力に正解した場合、さらに 20 点。
  • M=1 を満たす全ての入力に正解した場合、さらに 20 点。
  • すべてのテストケースに正解した場合、さらに 30 点が追加され、合計で 100 点となる。

出力

高橋君がすべてのアイドルを集めるために最適な戦略を取った場合、必要な金額の期待値を求めなさい。
出力は絶対誤差あるいは相対誤差の少なくとも片方が 10^{-6} 以下であれば許容される。
なお、出力の最後には改行をいれること。

解き方が解らない方へ

この問題は、非常に多くの部分点が設定されています。満点が取れる解法が解らない場合も、部分点だけを狙ったコードを提出してみましょう。
また、D問題の難易度も同程度となっております。両方の問題を読んでみることをお勧めします。

入力例 1

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

出力例 1

9343.17042606516
  • アイドルは 5 種類、くじは 2 種類です。
    1. 1 番目のくじでは 2 種類のアイドルを獲得することができ、1 回ごとに費用が 300 だけかかります。
      • 1 番目のくじに含まれる 1 番目のアイドルは、アイドル 3 で、出現確率は 5% です。
      • 1 番目のくじに含まれる 2 番目のアイドルは、アイドル 4 で、出現確率は 95% です。
    2. 2 番目のくじでは 3 種類のアイドルを獲得することができ、1 回ごとに費用が 500 だけかかります。
      • 2 番目のくじに含まれる 1 番目のアイドルは、アイドル 5 で、出現確率は 20% です。
      • 2 番目のくじに含まれる 2 番目のアイドルは、アイドル 1 で、出現確率は 30% です。
      • 2 番目のくじに含まれる 3 番目のアイドルは、アイドル 2 で、出現確率は 50% です。
  • この入力では、2 つのくじで手に入るアイドルが全て違います。
  • 1 つめのくじでかかる金額が 6015.789473684 、2 つめのくじでかかる金額が 3327.380952381 なので、合わせて 9343.17042606516 が答えとなります。

入力例 2

3 3
1 10
1 100
1 10
2 100
1 10
3 100

出力例 2

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

入力例 3

1 1
1 1000
1 100

出力例 3

1000
  • アイドルもくじも 1つずつしかないので、くじを 1 回引くだけで良いです。

入力例 4

2 2
2 1000
1 30
2 70
2 800
1 80
2 20

出力例 4

2128.57142857143

入力例 5

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

出力例 5

30333.4291970656