最近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とかだと実際ListとIntMapくらいあれば十分なことが多い印象。他の言語でアルゴリズムとかを学んだことがあって、そういうアルゴリズムを使いたいから「破壊的代入がしたい」みたいな人がいればMArrayとかIOArrayとか使えばいいんじゃないですかね。私がそういうのを全く知らないのでIOなしでも困ってないというだけかも。
実装
個人的によく使うのは以下の3つの実装
- 全探索(+枝刈り)
- DP
- メモ化再帰
全探索+枝刈り
普通に再帰。ガードが便利。問題によってはこれで十分。
solve = iter 0 where
iter n
| f n == True = False
| otherwise = iter ...
DP
終了条件付きのアルゴリズムでDPしたいときはunfoldrで大体なんとかなる(なんとかならない難しい問題もあるけど)。ある操作をn回繰り返したときの値が欲しい(予めnがわかっている時)はiterateやscanlで十分なこともある。
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"