E - Roulettes Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 475 点

問題文

N 台のルーレットがあります。 i 番目 (1\leq i\leq N) のルーレットには P _ i 個の整数 S _ {i,1},S _ {i,2},\ldots,S _ {i,P _ i} が書かれており、C _ i 円支払うことで 1 回プレイできます。 i 番目のルーレットを 1 回プレイすると、1 以上 P _ i 以下の整数 j が一様ランダムに選ばれ、S _ {i,j} ポイントを得ることができます。

ルーレットで得られるポイントは、過去の結果と独立に決まります。

高橋くんは、ポイントを M ポイント以上獲得したいです。 高橋くんは、M ポイント以上獲得するまでに支払う金額をなるべく小さくするように行動します。 ただし、高橋くんはルーレットをプレイするたびこれまでのルーレットの結果を見て次にプレイするルーレットを選ぶことができます。

高橋くんがポイントを M ポイント以上獲得するまでに支払う金額の期待値を求めてください。

より厳密な定義

より厳密には、次のようになります。 高橋くんがルーレットを選ぶ戦略を決めるごとに、その戦略で M ポイント以上獲得するまでに支払う金額の期待値 E が次のように定義されます。

  • 自然数 X に対して、その戦略に従って高橋くんが M ポイント以上獲得するか、ルーレットを X 回プレイするまでに支払う金額の期待値を f(X) とする。E=\displaystyle\lim _ {X\to+\infty}f(X) とする。

この問題の条件のもとで、高橋くんがどのような戦略をとっても \displaystyle\lim _ {X\to+\infty}f(X) が有限の値になることが証明できます。 高橋くんが E を最小にするような戦略をとったときの E の値を求めてください。

制約

  • 1\leq N\leq 100
  • 1\leq M\leq 100
  • 1\leq C _ i\leq 10 ^ 4\ (1\leq i\leq N)
  • 1\leq P _ i\leq 100\ (1\leq i\leq N)
  • 0\leq S _ {i,j}\leq M\ (1\leq i\leq N,1\leq j\leq P _ i)
  • \displaystyle\sum _ {j=1}^{P _ i}S _ {i,j}\gt0\ (1\leq i\leq N)
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N M
C _ 1 P _ 1 S _ {1,1} S _ {1,2} \ldots S _ {1,P _ 1}
C _ 2 P _ 2 S _ {2,1} S _ {2,2} \ldots S _ {2,P _ 2}
\vdots
C _ N P _ N S _ {N,1} S _ {N,2} \ldots S _ {N,P _ N}

出力

高橋くんが M ポイント以上獲得するまでに支払う金額の期待値を 1 行で出力せよ。 出力された値と真の値の相対誤差もしくは絶対誤差が 10 ^ {-5} 以下のとき、正答と判定される。

入力例 1

3 14
100 2 5 9
50 4 1 2 4 8
70 5 2 4 2 8 8

出力例 1

215.913355350494384765625

例えば、高橋くんはルーレットを次のようにプレイすることができます。

  • 50 円を支払ってルーレット 2 をプレイする。S _ {2,4}=8 ポイントを得る。
  • 50 円を支払ってルーレット 2 をプレイする。S _ {2,1}=1 ポイントを得る。
  • 100 円を支払ってルーレット 1 をプレイする。S _ {1,1}=5 ポイントを得る。得たポイントの合計が 8+1+5\geq14 ポイントとなったため、終了する。

この例では、14 ポイントを得るまでに 200 円を支払っています。

出力と真の値の相対誤差もしくは絶対誤差が 10 ^ {-5} 以下のとき正答と判定されるため、215.9112 や 215.9155 などと出力しても正解になります。

入力例 2

2 100
1 2 1 2
10 6 0 0 0 0 0 100

出力例 2

60

100 ポイントが出るまでルーレット 2 を回し続けるのが最適です。

入力例 3

20 90
3252 9 0 4 2 7 3 2 3 2 4
2147 1 1
4033 8 0 4 1 7 5 2 5 0
3795 6 6 6 2 3 2 2
3941 7 2 4 4 7 2 0 5
2815 6 2 1 0 5 2 2
3020 2 3 6
3858 9 4 2 7 3 0 4 4 6 5
4533 10 3 6 4 0 6 4 4 2 7 7
4198 8 6 7 0 6 3 6 5 6
3739 8 2 7 1 5 1 4 4 7
2465 4 1 4 0 1
4418 9 7 6 2 4 6 1 5 0 7
5450 12 0 4 4 7 7 4 4 5 4 5 3 7
4196 9 1 6 5 5 7 2 3 6 3
4776 9 2 2 7 3 6 6 1 6 6
2286 3 3 5 6
3152 3 4 1 5
3509 7 0 6 7 0 1 0 3
2913 6 0 1 5 0 5 6

出力例 3

45037.072314895291126319493887599716

Score : 475 points

Problem Statement

There are N roulette wheels. The i-th (1\leq i\leq N) wheel has P _ i integers S _ {i,1},S _ {i,2},\ldots,S _ {i,P _ i} written on it, and you can play it once by paying C _ i yen. When you play the i-th wheel once, an integer j between 1 and P _ i, inclusive, is chosen uniformly at random, and you earn S _ {i,j} points.

The points you earn from the wheels are determined independently of past results.

Takahashi wants to earn at least M points. Takahashi will act to minimize the amount of money he pays before he earns at least M points. After each play, he can choose which wheel to play next based on the previous results.

Find the expected amount of money Takahashi will pay before he earns at least M points.

More formal definition

Here is a more formal statement. For a strategy that Takahashi can adopt in choosing which wheel to play, the expected amount of money E that he pays before he earns at least M points with that strategy is defined as follows.

  • For a natural number X, let f(X) be the expected amount of money Takahashi pays before he earns at least M points or plays the wheels X times in total according to that strategy. Let E=\displaystyle\lim _ {X\to+\infty}f(X).

Under the conditions of this problem, it can be proved that \displaystyle\lim _ {X\to+\infty}f(X) is finite no matter what strategy Takahashi adopts. Find the value of E when he adopts a strategy that minimizes E.

Constraints

  • 1\leq N\leq 100
  • 1\leq M\leq 100
  • 1\leq C _ i\leq 10 ^ 4\ (1\leq i\leq N)
  • 1\leq P _ i\leq 100\ (1\leq i\leq N)
  • 0\leq S _ {i,j}\leq M\ (1\leq i\leq N,1\leq j\leq P _ i)
  • \displaystyle\sum _ {j=1}^{P _ i}S _ {i,j}\gt0\ (1\leq i\leq N)
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
C _ 1 P _ 1 S _ {1,1} S _ {1,2} \ldots S _ {1,P _ 1}
C _ 2 P _ 2 S _ {2,1} S _ {2,2} \ldots S _ {2,P _ 2}
\vdots
C _ N P _ N S _ {N,1} S _ {N,2} \ldots S _ {N,P _ N}

Output

Print the expected amount of money Takahashi will pay until he earns at least M points in a single line. Your output will be considered correct when the relative or absolute error from the true value is at most 10 ^ {-5}.

Sample Input 1

3 14
100 2 5 9
50 4 1 2 4 8
70 5 2 4 2 8 8

Sample Output 1

215.913355350494384765625

For instance, Takahashi can play the wheels as follows.

  • Pay 50 yen to play roulette 2 and earn S _ {2,4}=8 points.
  • Pay 50 yen to play roulette 2 and earn S _ {2,1}=1 point.
  • Pay 100 yen to play roulette 1 and earn S _ {1,1}=5 points. He has earned a total of 8+1+5\geq14 points, so he quits playing.

In this case, he pays 200 yen before earning 14 points.

Your output will be considered correct when the relative or absolute error from the true value is at most 10 ^ {-5}, so outputs such as 215.9112 and 215.9155 would also be considered correct.

Sample Input 2

2 100
1 2 1 2
10 6 0 0 0 0 0 100

Sample Output 2

60

It is optimal to keep spinning roulette 2 until you get 100 points.

Sample Input 3

20 90
3252 9 0 4 2 7 3 2 3 2 4
2147 1 1
4033 8 0 4 1 7 5 2 5 0
3795 6 6 6 2 3 2 2
3941 7 2 4 4 7 2 0 5
2815 6 2 1 0 5 2 2
3020 2 3 6
3858 9 4 2 7 3 0 4 4 6 5
4533 10 3 6 4 0 6 4 4 2 7 7
4198 8 6 7 0 6 3 6 5 6
3739 8 2 7 1 5 1 4 4 7
2465 4 1 4 0 1
4418 9 7 6 2 4 6 1 5 0 7
5450 12 0 4 4 7 7 4 4 5 4 5 3 7
4196 9 1 6 5 5 7 2 3 6 3
4776 9 2 2 7 3 6 6 1 6 6
2286 3 3 5 6
3152 3 4 1 5
3509 7 0 6 7 0 1 0 3
2913 6 0 1 5 0 5 6

Sample Output 3

45037.072314895291126319493887599716