LoginSignup
76

More than 5 years have passed since last update.

Haskell競技プログラミング入門

Last updated at Posted at 2014-07-31

最近HaskellでAtCoderとかProject Eulerとか解いたりして学んだことのまとめ。

入出力

入力の形式はだいたい決まっているのでいつもこれを書く。

import Control.Applicative

main = do
  -- "L M N" ---> [L,M,N]
  n <- fmap (read :: String -> Int) . words <$> getLine
  -- 複数行バージョン
  ns <- fmap (fmap (read :: String -> Int) . words) . lines <$> getContents

出力は場合によりけり。

import Text.Printf

main = do
  printf "%04d" 10 -- 4桁0詰め
  mapM_ print [1,2,3] -- リストの中身を1行ずつ出力

データ構造

普通にアプリケーション作っているときは気にしなかったけど、競プロだと時間がないとかドキュメント読んでる場合じゃないとかオンラインジャッジの環境が古いとかいう理由でデータ構造の選択にはほとんど余地がないことが多い。
自分の場合はだいたいこう:

  • 速度にこだわらない/先頭への追加しかしない: List
  • メモ化再帰のメモ: Array使う人が多いけどIntMapでも別にいいんじゃない?(と個人的には思っている)
  • それ以外(ランダムアクセス・挿入・削除・優先度付きキューを使いたい): IntMap

ABCとかだと実際ListIntMapくらいあれば十分なことが多い印象。他の言語でアルゴリズムとかを学んだことがあって、そういうアルゴリズムを使いたいから「破壊的代入がしたい」みたいな人がいればMArrayとかIOArrayとか使えばいいんじゃないですかね。私がそういうのを全く知らないのでIOなしでも困ってないというだけかも。

実装

個人的によく使うのは以下の3つの実装

  • 全探索(+枝刈り)
  • DP
  • メモ化再帰

全探索+枝刈り

普通に再帰。ガードが便利。問題によってはこれで十分。

solve = iter 0 where
  iter n
    | f n == True = False
    | otherwise = iter ...

DP

終了条件付きのアルゴリズムでDPしたいときはunfoldrで大体なんとかなる(なんとかならない難しい問題もあるけど)。ある操作をn回繰り返したときの値が欲しい(予めnがわかっている時)はiteratescanlで十分なこともある。

import Data.List

solve = head $ unfoldr next b where
  next :: b -> Maybe (a,b)
  next n
    | f n == True = Nothing -- 終了条件のところでNothing
    | otherwise = Just (a,n') -- aが答え, n'はnの次の値

メモ化再帰

最近はunfoldrがお気に入りなのであんまりメモ化再帰はしなくなったけど、たまに使う。
メモ化には(標準パッケージに入っているという理由で)Data.Arrayがよく使われている印象。

import Data.Array

solve n = iter i where
  memo = listArray (0,n) $ fmap iter $ [0..n]

  iter 0 = False
  iter i = f $ memo ! i

memoを作っておいて、iterの中ではiter iの代わりにmemo ! iとすることでメモ化された値を参照してくれる。
何も考えずに再帰を書いてしまい、「やっぱメモ化するかー」となったときには書き換える範囲が少なくて済むのが利点。

実装例

フィボナッチ数

fib n = fst $ iterate (\(a,b) -> (b,a+b)) (1,1) !! n

素数列

エラトステネスじゃないので注意。めっちゃ速くはないけどめっちゃ遅くもないので大体これ。

primes = 2:3:[x|i<-[1..], j<-[-1,1], let x = 6*i+j, isPrime x] where
  isPrime n = null [i|i<-takeWhile (\x -> x*x <= n) primes, rem n i == 0]

組み合わせ数(combination)

パスカルの三角形を使う。n,rがかなり小さくて下の実装が思いつかなければproduct [n-r+1..n]/product [1..r]でもいいけれど。

comb n r = iterate (scanl1 (+)) [1,1..] !! (n-r) !! r

Collatz数列

普通にunfoldr
fmap collatz [1..n]の最大値を求めるような問題でnが十分大きい時は適当にメモ化した方がいいかも。

collatz n = unfoldr next n where
  next k
    | k == 0 = Nothing
    | k == 1 = Just (k,0)
    | k `mod` 2 == 0 = Just (k,k `div` 2)
    | otherwise = Just (k,3*k+1)

Tips

知ってると微妙にお得な感じ。

ペアのリストをソート

Ord a => [(a,b)]aの値をキーにしてソートしたい

import Data.Function (on)
-- on :: (b -> b -> c) -> (a -> b) -> a -> a -> c

sortBy (compare `on` fst) ...
sortBy (comparing fst) ...  -- これも同じ

辞書順ソート

(Ord a,Ord b) => Ord (a,b)というinstanceがあって、辞書順になるように定義されているので辞書順ソートしたかったらとりあえずタプルのリストにしてしまう。

順列と組み合わせ

ただの順列。

import Data.List

-- ["abc","bac","cba","bca","cab","acb"]
permutations "abc"

重複ありの、長さrの部分リストの順列。最初に見た時は覚えておくと便利そうだなと思ったけど今まで役に立ったことがない。

import Control.Monad

-- ["aa","ab","ac","ad","ae","ba","bb","bc","bd","be","ca","cb","cc","cd","ce","da","db","dc","dd","de","ea","eb","ec","ed","ee"]
replicateM 2 "abcde"

部分リストの組み合わせはこう。

import Data.List

-- ["","a","b","ab","c","ac","bc","abc"]
subsequences "abc"

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
76