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 = 0

そして、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 = 0

main = print.fst.fromJust.msum.map (find((>5000).snd).cArray).iterate (2*) $100

はじめはどうにもこうにも、うごかなっかた。
xとyを書き間違えていたという、超初歩的ミス。ナンテコッタイ。

素数リストを扱っているのでさっきより面倒だが、それほど手間ではない。
msumで見つからなかったら探索範囲を2倍にしている。
が結論から言うと意味なし。

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