Problem 147

http://projecteuler.net/index.php?section=problems&id=147
長方形の数を数える簡単なお仕事。
やることは単純だが、結構難しい。
とりあず、長方形の変わりに格子点で考えた。
あとは領域内に何点あるかを数えればいいだけ。
場合わけがめんどくさい。
そして、計算結果を再利用するため、DP。

import Data.Array 

main = print.rect$ (47,43)

rect (n,m) = sum.elems$ r
    where r = listArray b.map g.range$ b ::Array (Integer,Integer) Integer
          b = ((1,1),(n,m))
          g (n,1) = div (n*(n+1)) 2 + n - 1
          g (n,m) | n < m = r!(m,n)
                  | otherwise = r!(n,m-1) + add(n,m) + div (m*n*(n+1)) 2

add (n,m) = sum.map count.zip [1..2*n-1].cycle $ [1,0]
    where count (x0,y0) = let u x | x < 2*n-x0 =min (2*m) $ x + x0 + y0
                                  | otherwise = min (2*m) $ 4*n-x-x0+y0
                              y x = abs(x-x0) + y0
                          in sum.map (\x -> div (max 0 $ u x - y x) 2)$[0..2*n]