Haskellで蟻本 CHAPTER 1

Haskellで蟻本 Haskell

はじめに

プログラミングコンテストチャレンジブック（通称「蟻本」）を買ったので、Haskellのコードに落とすチャレンジをしようと思います。解説は基本的にしないつもりです。

目標とする計算量が達成できたらOKということにします。バージョンはGHC8.8.3です。

CHAPTER 1

1-1

くじびき

replicateMがとても便利ですね。

import Control.Monad

main = do
  [n, m] <- map read . words <$> getLine
  k <- map read . words <$> getLine
  putStrLn $ if solve n m k then "Yes" else "No"

solve n m k = m `elem` [ sum abcd | abcd <- replicateM 4 k ]

1-3

くじびき

出力も省略します。ついでに、YesかNoならBoolにしてしまいます。

import Control.Monad

solve n m k = m `elem` [ sum abcd | abcd <- replicateM 4 k ]

1-6

三角形

sublistがけっこうきれいに書けて嬉しい。

import Data.List

solve n a = maximum $ 0 : [
  sum es | es <- sublist 3 a, 2 * maximum es < sum es]

sublist 0 _ = [[]]
sublist k xs
  = [ y:zs | (y:ys) <- tails xs, zs <- sublist (k-1) ys]

Ants

solve l n x = (minT, maxT) where
  minT = maximum [ min x (l-x) | x <- x ]
  maxT = maximum [ max x (l-x) | x <- x ]

くじびき

二分探索はめんどくさかった……。これがO(n³ log n)

import Control.Monad
import Data.Set

solve n m k = any pred [ sum abc | abc <- replicateM 3 k ] where
  pred x = (m-x) `member` fromList k

これがO(n² log n)です。

import Control.Monad
import Data.Set

solve n m k = any pred kk where
  pred x = (m-x) `member` fromList kk
  kk = [ sum ab | ab <- replicateM 2 k ]

おわりに

とりあえずここまで。続く、かも。