🌊

2020/11/07に公開

## 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)

``````-- 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

``````

## 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'' に入れたキューとなる。