Problem 232

Project Euler Haskell

232 The Race
Problem 232 - Project Euler
コインゲームの勝率を求める問題．
こういうゲームは選択肢が多いほうが有利に決まっている．
典型的な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  = 0
                 | otherwise = ps ! (p1, p2)
    where ( (0,0), (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, 0) + 0.5 * ps ! (1, 0)
    where ps = listArray ( (0,0), (u,u) ).map (bestProb u (prob ps)).range $ ( (0,0), (u,u) )

main :: IO ()
main = print $ p232 100

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