HaskellでProjectEuler+やってみた

ProjectEuler+ is 何

Project Eulerの問題を競技プログラミング風の入力形式で出題し、ジャッジしてくれる。 HackerRank上で行われているコンテスト形式ではあるが、"Open Indefinitely"とあり、いつでも挑戦できる。

今回はとりあえず#1に挑戦。

問題概要

T個のNに対して、N未満の3または5の倍数になっている数字の総和を求めよ。

とりあえず愚直に

import Control.Monad

solve :: Int -> Int
solve n = sum [x | x <- [1..n-1], mod x 3 == 0 || mod x 5 == 0]

main = do
  t <- readLn
  n <- replicateM t readLn
  mapM print $ map solve n

実行して見るが、"Terminated due to timeout"ではじかれる。
どうやら制限時間は5秒に設定されているらしい･･･

とりあえず時間がかかってそうなsumを正格版に書き直してみる。

solve n = foldl' (+) [x | x <- [1..n-1], mod x 3 == 0 || mod x 5 == 0]

が、結果変わらず。。。

制約を見てみる

1 ≦ T ≦ 10⁵
1 ≦ N ≦ 10⁹

･･････えっ
最大ケースってどんな速い言語でも無理なんじゃ･･･?

解法を見直し

3または5の倍数のふるいをかける部分をできるだけ小さくする。

solve n = s + t + sum [x | x <- [p*15+1..m], mod x 3 == 0 || mod x 5 == 0]
  where
    p = div m 15
    q = mod m 15
    m = n - 1
    s = p * sum l
    t = sum [0..p-1] * 15 * length l
    l = [x | x <- [1..15], mod x 3 == 0 || mod x 5 == 0]

これでいけると思いきや、まだ"Terminated due to timeout"の判定。
どうしようもないのでsumの部分を計算してマジックナンバーにした。

solve n = s + t + sum [x | x <- [p*15+1..m], mod x 3 == 0 || mod x 5 == 0]
  where
    p = div m 15
    q = mod m 15
    m = n - 1
    s = p * 60
    t = u * 15 * 7
    u = div (p * (p-1)) 2

これで何とかSuccess。むずかった･･･