Problem 78

http://projecteuler.net/index.php?section=problems&id=78
今までと同じ方法はかなり時間がかかる。
まぁ、そこで、google先生ですよ。
結果できたのが下。

import Data.List
import Data.Array.IArray
import Data.Maybe
import Control.Monad

ini = array (0,0) [(0,1)]::Array Integer Integer

piles l a m = ps
    where ps = listArray (0,m) $ elems a++[p n `mod` l | n<-[m'+1..m]]
             ::Array Integer Integer
          (0,m') = bounds a
          p n = sum [(s*).(ps!)$n-k|(s,k) <- takeWhile((<=n).snd) penta]

penta = zip  (cycle [1,1,-1,-1]).
        concat.zipWith(\ a b -> [a,b])(scanl1(+)[1,4..]) $ scanl1(+)[2,5..]

main = print.fst.fromJust.msum.
       map (find((==0).snd).assocs).scanl (piles$10^6) ini.iterate (2*) $100

DP。
先と同様に所与の探索範囲で見つからなかったら、探索範囲を2倍にしてもう一度DPを行うが
この際、前の計算結果を利用しているのが高速化の工夫その１。
（これで倍速ぐらいになると思われる。前は面倒だからやっていなかった。）
その２はmodをとっていること。多倍長の計算は時間がかかる。
必要なのは10^6で割ったあまりだけ。
実際これも倍速ぐらいになった。