2026-11-18
Chain.hs
cost :: [(Int, Int)] -> Int
cost [] = 0
cost [_] = 0
cost ms@((p, _) : _) =
minimum
[ cost l + cost r + p * q * s
| k <- [1 .. length ms - 1]
, let (l, r) = splitAt k ms
q = snd (last l)
]
where
s = snd (last ms)
main :: IO ()
main = print (cost [(9, 1), (1, 9), (9, 1)])
これは何を出力するでしょうか?
Answer
Output
18
cost は、並び ms を splitAt k で左右に分ける分け方をすべて試し、その中で最小の値を返します。値は、左右それぞれの cost に、p * q * s を足したものです。p は並び全体の先頭の組の1つ目、q は左側の最後の組の2つ目、s は並び全体の最後の組の2つ目です。要素が1つの並びは分けられないので 0 です。1
[(9, 1), (1, 9), (9, 1)] の分け方は2通りあります。k = 1 では左が [(9, 1)] で 0、右の [(1, 9), (9, 1)] は 1 * 9 * 1 = 9 です。分けた位置の費用は、p = 9、q = 1、s = 1 で 9 なので、合計は 18 になります。k = 2 では左の [(9, 1), (1, 9)] が 9 * 1 * 9 = 81、右が 0 で、分けた位置の費用は q = 9 から 9 * 9 * 1 = 81 となり、合計は 162 です。minimum は小さいほうの 18 を選びます。
左から順に1つずつまとめる分け方だけを思い浮かべると、162 と答えてしまいます。q は左側の最後の組から取るので、分ける位置によって 1 にも 9 にもなり、それが外側の掛け算の大きさを決めます。リスト内包表記が k のすべての値を試しているのは、この差がどの分け方で小さくなるかを、実際に比べないと決められないからです。
- 組
(p, q)を p 行 q 列の行列と読むと、costは行列を左から並んだ順に掛けるときの、数どうしの掛け算の最小回数です。p 行 q 列と q 行 s 列の行列の積には、p * q * s 回の掛け算が要ります。