トップ 差分 一覧 ソース 検索 ヘルプ RSS ログイン

確率・期待値

[アルゴリズム,競技プログラミング]

確率・期待値

  確率

  期待値

普通に期待値の求め方を忘れているので、復習。

期待値の求め方

期待値とはある試行を行ったとき、その結果として得られる数値の平均値のことである。

すなわち、試行によって得られる数値 Xx%5F1%2Cx%5F2%2Cx%5F3%2C%2E%2E%2E%2Cx%5Fn であり、

それぞれの値をとる確率が p%5F1%2Cp%5F2%2Cp%5F3%2C%2E%2E%2E%2Cp%5Fn とすると,X の期待値は,

期待値 = x%5F1+%5Ccdot+p%5F1+%2B+x%5F2+%5Ccdot+p%5F2+%2B+x%5F3+%5Ccdot+p%5F3+%2B+%2E%2E%2E+%2B+x%5Fn+%5Ccdot+p%5Fn++ となる。

実践

まあ、そもそもこのページを作ったのも以下の問題で苦杯をなめたからだ。

コードベースでこれを文書化すると

  • まず、全ての場合というのは1(=100%)になるはず
    • 最初に、全問正解を一発でできる確率を考えると、それはもちろん 1/2 となる
    • よって、期待値は E = 1/2 * p + ? * (1-p)
lines = $stdin.read
array = lines.split("\n")
 
N,M = array[0].split(" ").map(&:to_i)
 
# E = 1/p
# p = 1/2^M
_2m = 2**M
time = _2m * 1900*M + _2m * 100 * (N-M)
 
puts time

お名前: コメント: