Problem 232

232 The Race

コインゲームの勝率を求める問題．

こういうゲームは選択肢が多いほうが有利に決まっている．

典型的なDPだと思う．

現在の得点を状態として，DPを組んだ．

確率の計算に手間取ったのは秘密だ．

import Data.Array (Array, (!), listArray, range, bounds)
prob :: Array (Int, Int) Double -> (Int, Int) -> Double
prob ps (p1, p2) | p2 >= u  = 1
| p1 >= u  = 
| otherwise = ps ! (p1, p2)
where ( (,), (u,_) ) = bounds ps
bestProb :: Int -> ( (Int, Int) -> Double) -> (Int, Int) -> Double
bestProb u pr (p1, p2) =
maximum [
( pr (p1 + 1, p2 + q) + pr (p1, p2 + q) + pr (p1 + 1, p2) * ( d - 1 ) ) / ( d + 1 )
| t <- [1..1+u_t] , let q = 2 ^ (t - 1), let d = 2 ** fromIntegral t]
where u_t = ceiling.logBase 2.fromIntegral $ u - p2
p232 :: Int -> Double
p232 u = 0.5 * ps ! (, ) + 0.5 * ps ! (1, )
where ps = listArray ( (,), (u,u) ).map (bestProb u (prob ps)).range $ ( (,), (u,u) )
main :: IO ()
main = print $ p232 100

はじめ，Arrayではなく，UArrayをつかっていて，遅延評価が効かず，途方に暮れていた．

まったく，阿呆ですね．

コンテンツ