Problem 113

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

とりあえず、再帰式を考えて、DPにした。

しかし、かなりきれいな再帰式なので手計算できそうではある。が、いいや。

import Data.Array.IArray
n = 100
mkArray :: (Ix i)=> (i -> Integer)-> (i,i)->Array i Integer
mkArray f b = listArray b. map f . range $ b
descend = mkArray dsc ((1,),(n,8))
dsc (1,m) = m+1
dsc (d'+1,m) = sum [descend!(d',k)|k<-[..m]]
ascend = mkArray asc ((1,2),(n,10))
asc (1,m) = 10 - m
asc (d'+1,m) = sum [ascend!(d',k)|k<-[m..9]]
notBouncy = mkArray b (1,n)
where b 1 = 10
b (d+1) = sum [descend!(k,l-1) + ascend!(k,l+1) | k<-[1..d],l<-[1..9]] + 9 + notBouncy! d
main = print$ notBouncy ! n - 1

追記

notBouncy n = descend + ascend - 10
where descend = product [n+1..n+9] `div` product [1..9] -- use [0..9]
ascend = product [n+1..n+8] `div` product [1..8] -- use [1..9] , no leading 0
p113 n = sum.map notBouncy $ [1..n]

重複組み合わせでした．

コンテンツ

追記