Problem 77

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

Problem 76とまったく同じ方針で解ける。

まず再帰。

count x = count' x primes
count' x (p:ps) | x > p = count' (x-p) (p:ps) + count' x ps
| x ==p = 1
| x < p = 

そして、DPに書き換える。何番目の素数から使うか、でインデックス。

import Number
import Data.Array.IArray
import Data.List
import Data.Maybe
import Control.Arrow
import Control.Monad
cArray x = map (fst.fst&&&snd).filter((==1).snd.fst).assocs$c
where c = listArray((1,1),(x,length ps'))
[count y p|y<-[1..x],p<-[1..length ps']]
::Array (Int,Int) Int
ps = listArray(1,length ps')ps'::Array Int Int
ps' = takeWhile(<=x).map fromInteger$primes
count y p | y > ps!p && p==length ps' = c!(y-ps!p,p)
| y > ps!p = c!(y,p+1)+c!(y-ps!p,p)
| y ==ps!p = 1
| y < ps!p = 
main = print.fst.fromJust.msum.map (find((>5000).snd).cArray).iterate (2*) $100

はじめはどうにもこうにも、うごかなっかた。

xとyを書き間違えていたという、超初歩的ミス。ナンテコッタイ。

素数リストを扱っているのでさっきより面倒だが、それほど手間ではない。

msumで見つからなかったら探索範囲を2倍にしている。

が結論から言うと意味なし。

予想以上に高速に動いて、ちょっとうれしい。