Problem 109

http://projecteuler.net/index.php?section=problems&id=109

とりあえず、再帰で書いて、DPになおそうと思った。

import Data.List
score = sort$[1..20]++map (2*) [1..20]++map (3*) [1..20]++[25,50]
double = map (2*) $ [1..20]++[25]
finish0 n = map return$ filter (n==) double
finish1 xs n = map return .filter (n==) $ xs
finish2 [] _ = []
finish2 (x:xs) n = (map (x:).finish1 (x:xs))(n-x) ++ finish2 xs n
outWay n =finish0 n ++
concat[map (d:).finish1 score $ n -d |d<-double] ++
concat[map (d:).finish2 score $ n -d |d<-double,n-d>1]
p109 = print.sum.map (length.outWay)$[1..99]

DPにする前にためしに実行したら、遅くない。

これでいいや。