Problem 155

http://projecteuler.net/index.php?section=problems&id=155
メモリ不足になったりした。
素直なアルゴリズム。

import Data.Array
import qualified Data.Set as S

n = 18
main = print.sum.map S.size.elems$ caps
caps = listArray (1,n) $ (S.singleton 1) : map c' [2..n] :: Array Int (S.Set Rational)
    where c n = S.fromList $ do k <-[1..div n 2]
                                c1 <- S.toList$caps!k
                                c2 <- S.toList$caps!(n-k)
                                c <- [c1+c2,(c1*c2)/(c1+c2)]
                                return c
          c' n =  foldl (S.\\) (c n) $ map (caps!) [1..n-1]

遅いけど、このアルゴリズムをjavaで実装するのは面倒だ。
有理数クラスあるのかな？