💬
競プロやるぜ
周りに人たちに、競プロをやってる人が増えてきたので、そろそろやるぜ。
言語はHaskellを使う。これまで何度かHaskellに入門してきたけど、いつも完全に理解して終了しちゃうので、今回はちゃんと使ってみようと思う。
Haskell準備
- stackインストール
- stack new hoge で hogeプロジェクトを作成する。
- 入力データを標準入力から取るのが、だるいので当面変数に直書きする。
- ロジックは、src/Lib.hs にそのまま書く。名前もだるいので、someFuncのままだ。
- stack run
蟻本
ということで、蟻本を買ってきた。
蟻本のコードはC++（っていうかほぼC）で書かれている。
for文とかだるいので、Haskellはよい気がするが、使いこなせてない。
HaskellでArrayとかLoopとか使いだすと負けな気がする。それならC++で書く。
多分、使いこなせていないだけだろうけれど。
1-6 三角形
リスト内包表記を使えば、解けるんじゃね。と思ったら解けた。
module Lib
( someFunc
) where
import Data.List
targetNumbers = [2,3,4,5,10]
lsort = sortBy(\xs ys -> compare(fst xs) (fst ys))
three nums = [(x+y+z, (x, y, z)) | x <- nums, y <- nums, z <- nums,
x > y, x > z, y > z,
x < y + z]
someFunc :: IO ()
someFunc = print $ head $ reverse $ lsort $ three targetNumbers
わざわざ、「head $ reverse $ lsort」してるあたりがダサい。
1-6 蟻
C++ていうかほぼCのコードを単にHaskell化した。
module Lib
( someFunc
) where
l = 10
targetNumbers = [2,6,7]
mina = foldl(\acc x -> max acc (min x (l-x))) 0
maxa = foldl(\acc x -> max acc (max x (l-x))) 0
someFunc :: IO ()
someFunc = print $ show (mina targetNumbers) ++ " " ++ show (maxa targetNumbers)
- print表示のやり方がダサい。
- foldlじゃなくて、foldl1とかにした方がかっこいい気がする。
2-1 みんな大好きfib
このコードは、Haskellでフィボナッチ数列 〜Haskellで非実用的なコードを書いて悦に入るのはやめろ〜からパクった。
module Lib
( someFunc
) where
fib :: Int -> Integer
fib 0 = 0
fib 1 = 1
fib n = fibList !! (n - 2) + fibList !! (n - 1)
fibList :: [Integer]
fibList = map fib [0..]
someFunc :: IO ()
someFunc = putStrLn $ show $ fib 30
- !! とか忘れている。
- 無限リストはこうやって使えるんだ。
2-1 部分和問題（DFS:深さ優先探索）
これもC++コードの移植。
Haskellだからパターンマッチ使うぜ。
module Lib
( someFunc
) where
targetNumbers = [1,2,4,7]
kk = 13
dfs :: Int -> [Int] -> Int -> Bool
dfs sum [] k = sum == k
dfs sum (x:xs) k =
if dfs (sum+x) xs k then True
else dfs sum xs k
someFunc :: IO ()
someFunc = print $ dfs 0 targetNumbers kk
Discussion