(問題 10) サイコロ step.final Bash(Beta)編（paizaランク A 相当）

今度は 2 回までではなく、M 回まで振れることを考えてみましょう。

M - 1 回まで振れる場合の期待値がすでに計算できていると仮定します。このとき期待値は (1 回目で C が出たときの最終的なスコアの期待値) × 1/N を C = C_1, C_2, ..., C_N のときの総和をとったものになります。これは、問題 9 と同様、C が M - 1 回まで振れる場合の期待値より大きいか否かで期待値を最大化する戦略を決めることができ、それをもとに計算が出来ます。

1 回だけ振れる場合の期待値は簡単に求めることが出来ます。それをもとに、2 回だけ振れる場合の期待値をもとめ、またそれをもとに、3 回だけ振れる場合の期待値を求め…というように繰り返し計算することで M 回まで振れる場合の期待値も計算することが出来ます。

問題

各面の出る確率が等しい N 面のダイスがあり、このダイスを最大で M 回まで振ることができます。

最終的な出目が i (1 ≦ i ≦ N) のとき、スコアは C_i になります。スコアの期待値を最大化するような戦略を取ったときの期待値を求めてください。