No.155 生放送とBGM

レベル : / 実行時間制限 : 1ケース 6.000秒 / メモリ制限 : 512 MB / 小数誤差許容問題 絶対誤差または相対誤差が$10^{-9}$ 以下
タグ : / 解いたユーザー数 21
作問者 : LayCurseLayCurse

2 ProblemId : 183 / 出題時の順位表

問題文

ユキさんは生放送で配信する際に,BGMとしてクララーリスというグループの曲を流しています.
ユキさんのミュージックプレイヤーには,クララーリスの曲が $N$ 曲登録されており,その $k$ 曲目の長さは $S_k$ です.
また,ユキさんが生放送で配信する時間は $L$ 分です.
ミュージックプレイヤーはランダム再生機能があり,まず,登録されている曲をランダムに並べ替えて,順番に再生されます.
また,全ての曲が再生された後は,再びランダムに並び替えて,順番に再生されます.
ユキさんの放送中に $1$ 秒でも流れる曲は何曲になるかという期待値を求めるプログラムを書いて下さい.
ランダムに並べ替える際は,$N!$ パターンの並び替え方が等確率で起こるものとし,毎回独立に並び替えるとして下さい.
また,ユキさんは生放送が始まると同時に再生し始めます.

入力

$N$ $L$
$S_1$ $S_2$ $\cdots$ $S_N$

$1 \leq N \leq 50$
$1 \leq L \leq 300$
$S_k$ は $\verb|MM:SS|$ という形の文字列であり,その曲の長さが $\verb|MM|$ 分 $\verb|SS|$ 秒であることを表す($00 \leq \verb|MM|,\verb|SS| \leq 59$,かつ,$\verb|MM:SS| \neq 00\verb|:|00$)

出力

生放送において流れる曲数の期待値を $1$ 行で出力して下さい.
相対誤差が $10^{-9}$ 以下であれば正答とみなされます.
最後に改行してください.

サンプル

サンプル1
入力
5 30
10:30 20:47 08:14 29:59 05:24
出力
2.6

よくある生放送の放送時間は $30$ 分ですよね.
曲のデータの実際のデータを調べようかと思ったのですが面倒だったのでやめました.

サンプル2
入力
2 1
00:59 01:00
出力
1.5

$1$ 曲目が先に流れた場合は,$2$ 曲目が $1$ 秒流れるので,この場合流れた曲数は $2$ 曲です.
$2$ 曲目が先に流れた場合は,$1$ 曲目は流れないので,この場合流れた曲数は $1$ 曲です.
よって流れる曲数の平均値は $1.5$ 曲です.

サンプル3
入力
4 300
00:01 00:02 00:01 00:03
出力
4

同じ曲が何回も流れても $1$ 曲は $1$ 曲です.

提出ページヘ