torus711 のアレ

主に競技プログラミングの問題について書きます

Codeforces #185, Division 2, B : Archer

概要

二人のプレイヤーがターン制の的当てゲームをする。
それぞれのプレイヤーについて、一回の試行で命中させる確率が与えられる。
先に的に当てたプレイヤーが勝利としたとき、先攻のプレイヤーが勝つ確率を求めよ。

解法

先攻が勝つパターンは、先攻も後攻も外す という事象k \quad ( 0 \leq k ) 回繰り返した後に先攻が当てるというものです。
どのタイミングで当てるにしても、考慮される事象は独立な事象なので、確率を足し合わせることで和事象の確率を求められます。
また、k が十分大きくなると生起率は極めて小さくなります。
従って、k について十分な範囲のループを回して確率を足し合わせれば答えが求まり、誤差も許容範囲内に収まります。

コード

import Control.Applicative
import Control.Monad
import Data.List
import Text.Printf

main = do
	[ a, b, c, d ] <- map read . words <$> getLine
	printf "%.8f\n" $ solve 0 ( a / b ) ( c / d )

solve :: Int -> Double -> Double -> Double
solve 100000 _ _ = 0
solve depth prob1 prob2 = ( ( 1 - prob1 ) * ( 1 - prob2 ) ) ^ depth * prob1 + ( solve ( depth + 1 ) prob1 prob2 )