賛否両論なこの問題。自分は苦手かな…。
http://community.topcoder.com/stat?c=problem_statement&pm=15137
問題
これから天気予報を行う。
雨が降る確率はPであるとする。
ここで予報を行うと、それはN人を伝達して最終的に放送される。
i番目の人は確率D[i]で言われた内容をそのまま、(1-D[i])で反転させて伝えてしまう。
予報として雨が降る・降らないを選択できるとき、最終的に放送される予想の的中率を求めよ。
解法
雨が降ると予想したとき、1人仲介したときに実際にそう伝わる確率P'は
P' = P*D[i] + (1-P)*(1-D[i])
となる。
最終的に的中率を最大化したいので、全員に対し上記式を順次求めて、max(P',1-P')を答えればよい。
class RainForecast { public: double predictRain(int ilkoProb, vector <int> deliverProbs) { double a=ilkoProb/100.0; FORR(d,deliverProbs) a=(a*d+(1-a)*(100-d))/100.0; return max(a,1-a); } }
まとめ
うーん…。