Zenn
🌊

Haskellで蟻本やるぜ4（貪欲法）

2020/11/07に公開
Haskell
蟻本
tech

前回の続き。
今日からgreedy(貪欲法)だ。

2-2 硬貨の問題

コインを数えるぜ。ここを参考にしたお。

solve :: Int -> Int -> [(Int,Int)] -> Int
solve k a cs = go k a cs
    where
        -- 選ぶコインがなくなった
        go k _ [] = k
        -- 次のコインを取る
        go k a (x:xs) = go (k+r) (a-v) xs
            where
                -- コインの枚数
                r = min (a `div` (fst x)) (snd x)
                -- 価格
                v = r * (fst x)

main :: IO ()
main = do 
    let ret = solve 0 620 [(500,2),(100,0),(50,3),(10,1),(5,2),(1,3)]
    print ret

r = min (a `div` (fst x)) (snd x)

の箇所をうっかり

r = min (a / (fst x)) (snd x)

と書いてしまうと、「/」は少数も計算してしまうので、型が合わなくなってしまう。

区間スケジューリング問題

蟻本のロジックが本当に正しいのだろうか。。

-- 区間スケジューリング問題
-- https://lvs7k.github.io/posts/2018/11/pccb-easy-2/
import Data.List

-- lsort = sortBy(\xs ys -> compare(snd xs) (snd ys))

solve :: Int -> [(Int, Int)] -> Int
solve k [] = k
solve k ((s, e):xs) = solve (k + 1) (filter ((>= e) . fst) xs)

main :: IO ()
main = do
    let ss = [(2,5),(1,3),(4,7),(8,10),(6,9)]
    --let d = (lsort ss)
    let d = sortOn snd ss
    -- print d
    let ret = solve 0 d
    print ret

これまでタプルをソートするとき、いちいち lsort を定義していたが、 sortOn を使えばよい。
楽ちんだぜ。

Best Cow Line (POJ3617) - Saruman's Army (POJ 3069) - Fence Repair (POJ 3253)

丸パクリだぜ。ただし、q3の第１パラメータは不要なので削除。

-- https://lvs7k.github.io/posts/2018/11/pccb-easy-2/
import Data.List
import qualified Data.Set as S

-- Best Cow Line (POJ 3617)
q3 :: String -> String
q3 ss = reverse $ go "" ss
  where
    go ts "" = ts
    go ts us
        | us <= us' = go (head us  : ts) (tail us)
        | otherwise = go (head us' : ts) (tail us')
      where
        us' = reverse us

-- Saruman's Army (POJ 3069)
q4 :: Int -> [Int] -> Int
q4 r xs = go 0 (sort xs)
  where
    go k []     = k
    go k (y:ys) = go (k + 1) cs
      where
        (as, bs) = span (<= y + r) (y:ys)
        cs = dropWhile (<= last as + r) bs

-- Fence Repair (POJ 3253)
q5 :: Int -> [Int] -> Int
q5 n ls = go 0 n (S.fromList $ zip ls [1 ..])
  where
    go k m s
        | Just ((v1, _), s')  <- S.minView s
        , Just ((v2, _), s'') <- S.minView s'
            = go (k + v1 + v2) (m + 1) (S.insert (v1 + v2, m + 1) s'')
        | otherwise = k

main :: IO ()
main = do
    let a3 = q3 "ACDBCB"
    print a3
    let a4 = q4 10 [1,7,15,20,30,50]
    print a4
    let a5 = q5 3 [8,5,8]
    print a5

Best Cow Line (POJ 3617)

reverseしてものと比較して、headを取るかtailを取るか決めて、goの第2パラメータから、第１パラメータにうつしていく。
最後にreverseしたものが答えだ。

Saruman's Army (POJ 3069)

spanは、リストを、リストのうち条件を満たす要素からなる先頭列とその残りからなるタプルとして返す。参照
dropWhileと組み合わせて、カバーされていない地点を探していく。

Fence Repair (POJ 3253)

  • Just ((v1, _), s') <- S.minView s で、一番小さい板
  • Just ((v2, _), s'') <- S.minView s' で、二番目に小さい板
  • S.minViewに対して、fromList [(5,2),(8,1),(8,3)]を呼ぶと、Just ((5,2),fromList [(8,1),(8,3)])が返ってくる。
  • v1とv2には、それぞれ板の長さが入る
  • タプルは、(<値>, <識別番号>)となっている。「go k m s」のmが識別番号となる。
  • 識別番号を降っているのは、値が重複しないようにするためらしい。
  • kが最終的な１枚ものの板の長さとなる。
  • 再帰呼び出ししている go (k + v1 + v2) (m + 1) (S.insert (v1 + v2, m + 1) s'') は、
    • (k + v1 + v2) : 板の長さ
    • (m + 1) : 識別番号
    • (S.insert (v1 + v2, m + 1) s'') : タプル(v1とv2を足した長さ, 識別番号)を s'' に入れたキューとなる。

Discussion