Problem 191

素直なDP.
import Data.Map (Map,unionsWith,filterWithKey,mapKeysWith,fold,singleton)
type State = (Int,Int)
late,onTime,absent :: State -> State
late (a,l) = (,l+1)
onTime (_,l) = (,l)
absent (a,l) = (a+1,l)
day :: Map State Integer -> Map State Integer
day m = filterWithKey prize.unionsWith (+) $ [map' late m, map' onTime m, map' absent m]
where map' f = mapKeysWith (+) f
prize (a,l) _ = a < 3 && l < 2
p191 :: Int -> Integer
p191 n = fold (+) .(!!n).iterate day $ singleton (,) 1
コンテンツ
