💬

競プロやるぜ

2 min read

周りに人たちに、競プロをやってる人が増えてきたので、そろそろやるぜ。
言語はHaskellを使う。これまで何度かHaskellに入門してきたけど、いつも完全に理解して終了しちゃうので、今回はちゃんと使ってみようと思う。

Haskell準備

  • stackインストール
  • stack new hoge で hogeプロジェクトを作成する。
  • 入力データを標準入力から取るのが、だるいので当面変数に直書きする。
  • ロジックは、src/Lib.hs にそのまま書く。名前もだるいので、someFuncのままだ。
  • stack run

蟻本

ということで、蟻本を買ってきた。

https://book.mynavi.jp/supportsite/detail/9784839941062.html
蟻本のコードは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

ログインするとコメントできます