SRM577 div1 250

問題

プログラミングコンテストの部屋割りをする。
N人の登録があるとする。
Nが20で割り切れるなら、部屋数はN/20。割り切れないならN/20+1(/は、整数割り算を表す)。
レートについて降順にならべ、R人ずつ、ランダムに部屋がかぶらないように部屋を割り当てる。
これを繰り返すが、最後のグループはRに満たない場合がありうる。そのときも同様にランダムにかぶらないように割り当てる。

N人のレートが与えられる。そのうち1番目はあなたのレート。
あなたの部屋の(あなたのレートを含めた)レートの期待平均値を求める。

考え方

降順にならんだレートをR人ずつ処理するので、自分が含まれるグループのときは、ほかの人は同じ部屋になりえないので省く。
自分が含まれないグループの場合、同じ部屋になる確率は1/Rなので、そのグループで同じ部屋になるレートの期待値は、(そのグループの合計レート)/Rで求まる。
しかし、最後のグループは人が少ない場合があるので、「人が割り当てられる場合」と「人が割り当てられない場合」が考えられる。

割り当てられる場合と割り当てられない場合の確率は求められる。
割り当てられる場合、そのグループで同じ部屋になるレートの期待値は、上記と同様に求めればよい。
ここまでで、割り当てられる場合と割り当てられない場合について、それぞれ人数と各グループのレートの期待値がもとまっているので、それぞれの人数から、レートの期待平均値が求まる。

なので、最終的に、
「割り当てられる場合の確率*割り当てられる場合のレートの期待平均値」 + 「割り当てられない場合の確率*割り当てられない場合のレートの期待平均値」
が答えになる。