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,]
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  $ u x - y x) 2)$[..2*n]