きままにものづくり

日々の気付いたことなんかを書いてます。

SRM626Div1Easy

問題

AliceとBobがいる。Aliceはa個のb面あるサイコロを転がし、Bobはc個のd面あるサイコロを転がす。サイコロの目の合計が高い方が勝ちとする。Aliceが勝利する時のサイコロの目の期待値を求めよ。

解法

はじめに、スコアに対する確率分布を求める。
Aliceの場合の確率分布を P_aとし、スコアをxとして
 P_a(x) = f(x, a, b)
とする。
fを動的計画法を用いて求めていく。
 f(x, a, b) = {\displaystyle \sum^{min(b, x)}_{y=1}} f(x-y, a-1, b)
bは常に固定されているので、引数の組み合わせは a^2bとなる。
同様にBobの場合も求める。

計算量

 O(a^2 b^2)

コード

広告を非表示にする