wvogel日記

自分用の技術備忘録が多めです.

time over

問題はこちら

単純なアルゴリズムはすぐに完成しましたが、
残念なことに、以下のコードではタイムオーバー....
どうするのがよいでしょうか。
group関数で一まとめにしてやると早くなるのかな

与えられたデータセットが100000個の-1だから...
きっとこれは畳み込みがよくないんですね。
100000!回計算してるわけですから

import Data.List

answer :: [Int] -> Int
answer = sum.map countUp.tails

dataList :: String -> String -> [Int]
dataList n = map read.take (read n).words

countUp :: [Int] -> Int
countUp [] = 0
countUp [x] = 0
countUp (x:xs) = length $ filter ((==0).(+x)) xs

main = do n <- getLine
          cs <- getLine
          print.answer.dataList n $ cs