2026-11-18
Cut.hs
cut :: [Int] -> Int -> Int -> Int
cut cs a b = foldr min 0 (map split inside)
where
inside = [c | c <- cs, a < c, c < b]
split c = b - a + cut cs a c + cut cs c b
main :: IO ()
main = print (cut [2, 4, 7] 0 10)
a から b までの棒を、間にある位置 cs のすべてで切り分けるときの、費用の最小値を返す cut です。1回切るごとに、そのとき切った棒の長さだけ費用がかかり、どの位置から切るかで合計が変わります。0 から 10 までの棒を 2、4、7 で切る cut [2, 4, 7] 0 10 は 20 になるはずが、いまは 0 が返ります。
Answer
Wrong
cut :: [Int] -> Int -> Int -> Int
cut cs a b = foldr min 0 (map split inside)
foldr min 0 xs は、xs の要素と初期値の 0 をまとめて min にかけます。費用はどれも 0 以上なので、どの候補と比べても 0 が残り、cut はいつも 0 を返します。棒の間に切る位置が1つも無いときに 0 を返したくて初期値を 0 にしたのでしょうが、その 0 は候補があるときも比べる相手に加わってしまいます。
Right
cut :: [Int] -> Int -> Int -> Int
cut cs a b
| null inside = 0
| otherwise = minimum (map split inside)
切る位置が無い場合と有る場合を、ガードで分けます。inside が空なら費用は 0 で、空でなければ minimum を候補だけにかけるので、0 が紛れ込みません。minimum は空リストではエラーになりますが、空の場合は1つ目のガードが先に受けるので、そこへは届きません。0 から 10 の棒では、最初に 4 で切ると 10、残りの 0 から 4 を 2 で切ると 4、4 から 10 を 7 で切ると 6 で、合計の 20 が最小です。