Problem 191
Problem 191 - Project Euler
素直なDP.
import Data.Map (Map,unionsWith,filterWithKey,mapKeysWith,fold,singleton) type State = (Int,Int) late,onTime,absent :: State -> State late (a,l) = (0,l+1) onTime (_,l) = (0,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 (+) 0.(!!n).iterate day $ singleton (0,0) 1