Hatena::Grouptopcoder

TopCoder戦記

研究開発者・ellerのTopCoder挑戦記録。言語は主にJavaを使用しています。ドキュメンテーションコメントはSubmit完了後、ブログ掲載前に補完したものです。

2011-04-15

SRM467 Div2 Easy

| 23:00

以前Javaで書いた解答はこちら

メモ化なし

calculate :: Integer -> Integer -> Integer
calculate 0 n = n
calculate k n = sum $ map (calculate (k - 1)) [1..n]

main = print $ calculate 14 13

メモ化あり

参考:http://www.haskell.org/haskellwiki/Memoization

2引数関数をメモ化するのはややこしそうだったので、ビットシフトを使って1引数に2引数分の情報を持たせることに。

compress_shift = 16

calculate :: Int -> Int -> Int
calculate k n = calc $ compress k n
  where compress k n = k * compress_shift + n

calc :: Int -> Int
calc = let calc' c
             | c < compress_shift = c
             | otherwise          = sum $ map (calculate ((take_k c) - 1)) [1..(take_n c)]
       in (map calc' [0..] !!)
       where take_k c = c `div` compress_shift
             take_n c = mod c compress_shift

main = print $ calculate 14 13