SRM626Div1Easy
問題
AliceとBobがいる。Aliceはa個のb面あるサイコロを転がし、Bobはc個のd面あるサイコロを転がす。サイコロの目の合計が高い方が勝ちとする。Aliceが勝利する時のサイコロの目の期待値を求めよ。
解法
はじめに、スコアに対する確率分布を求める。
Aliceの場合の確率分布をとし、スコアをxとして
とする。
fを動的計画法を用いて求めていく。
bは常に固定されているので、引数の組み合わせはとなる。
同様にBobの場合も求める。
計算量