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 (,) [(,1)]::Array Integer Integer
piles l a m = ps
where ps = listArray (,m) $ elems a++[p n `mod` l | n<-[m'+1..m]]
::Array Integer Integer
(,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((==).snd).assocs).scanl (piles$10^6) ini.iterate (2*) $100

DP。

先と同様に所与の探索範囲で見つからなかったら、探索範囲を2倍にしてもう一度DPを行うが

この際、前の計算結果を利用しているのが高速化の工夫その１。

（これで倍速ぐらいになると思われる。前は面倒だからやっていなかった。）

その２はmodをとっていること。多倍長の計算は時間がかかる。

必要なのは10^6で割ったあまりだけ。

実際これも倍速ぐらいになった。