218.1

昨日の続き。ひどい問題だった...。

750

一回の勝負での勝率をPとしたときの、今までの対戦成績A勝B敗を実現する確率Qから、Pの期待値を計算し、残りN試合でK勝する確率を求めよという問題。

勝った場合はA+1勝B敗として、N-1試合でK-1勝する確率を、負けた場合はA勝B+1敗として、N-1試合でK勝する確率を求めるという問題。この部分を探索する必要があり、ちゃんとメモしないといけない。

問題はPの期待値を計算する部分。仕方がないので積分せざるを得ないので、p^A*(1-p)^Bを0から1まで積分すると、Qの総和が求まり、p*p^A*(1-p)^Bを0から1まで積分するとPの総和にQの総和をかけたものが求まる。(実際にはA勝B敗の可能な順列の数だけ乗算する必要があるけれど、最終的に除算をする必要があるので飛ばす。)これは単純にB回ループを回すだけ、なのだけれど、Bの大きさが高々100とはいえ、100C50とかやると当然のごとくdouble程度では溢れてしまうわけです。で、Javaを使っているので、なんだかなぁと思いつつBigDecimalを利用。scaleが良く分からないと思いつつ、取り敢えず100とか指定してみて実行。これで精度的な問題はクリアしました。

結局良く分からないマジックナンバーが残っているソースということで、非常に気持ちが悪い。ちゃんとBigDecimalの仕様くらい調べておいた方がいいのかなぁ？この手の問題でさっくり使えると非常に有利だとは思うけれども？有理数であることが保障されている問題だと思うので、これについてはBigIntegerを二つ使って分数を実現してもいいけれど、100から200までの積のオーダーの分母になり得るので、精度に確信が持てるならばBigDecimalを使った方がいいのかなぁ、という感じ。