AtCoder ABC322 振り返り

はじめに　

遅くなりましたが、2回目のAtCoder 振り返りです！
言語はHaskellです！

結果

前回と同じく、A, B 2完でCがTLEでした。
A, Bまでスムーズに解けたのですが、Cでつまづいてしまった感じです。

結果

レーティングは次の振り返りで投稿します。

問題の振り返り

A - First ABC 2

• 問題: https://atcoder.jp/contests/abc322/tasks/abc322_a

• 回答: https://atcoder.jp/contests/abc322/submissions/46084383

特に苦労はなかったです。 `isInfixOf` が便利でした。

B - Round-Robin Tournament

• 問題: https://atcoder.jp/contests/abc323/tasks/abc323_b

• 回答: https://atcoder.jp/contests/abc322/submissions/46095237

これも特に問題なかったです。

C - Festival

• 問題: https://atcoder.jp/contests/abc322/tasks/abc322_c

• 回答: https://atcoder.jp/contests/abc322/submissions/46119489

出力結果はあっていたのですが、会えなくTLEで撃沈しました。
原因はここで、ループごとにfindを実行してしまっていたので、O(N^2)になっていたのですね。そこに気づかずTLEで終わりました。

fireworkDays :: Int -> [Int] -> [Int]
fireworkDays n days = map distancesToNextFireWork [1 .. n]
  where
    s = S.fromList days
    distances = zip (0 : days) days
    distancesToNextFireWork i
      | S.member i s = 0
      | otherwise = snd (fromJust (find (\(start, end) -> i >= start && i <= end) distances)) - i

実際はこんな風に、差分を計算したリストを作れば、O(N)で計算できるのでACになります。(回答はhttps://atcoder.jp/contests/abc322/submissions/46149193に投稿しています。)

solve :: [Int] -> [Int]
solve as = fireworkDate 1 as
  where
    fireworkDate k aas@(a : as) = a - k : fireworkDate (succ k) (if a == k then as else aas)
    fireworkDate _ [] = []

反省としては、TLEになったとき計算量を抑える方法を考えることかな、ということです。（単純に修行量が足りないだけなのですが）
ちなみに、zipWithを使うともっとシンプルに解けるみたいです。(これはhttps://atcoder.jp/contests/abc322/submissions/46149412に投稿しています。)zipWith便利。

diff :: Num c => [c] -> [c]
diff lst = zipWith (-) lst (0 : init lst)

main :: IO ()
main = do
  _ <- BS.getLine
  as <- unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine

  let diffDates = map (+ (-1)) $ diff as
  let ans = diffDates >>= \date -> reverse [0 .. date]

  mapM_ print ans