Namaran

Code daily. Without assist.

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 のすべての値を試しているのは、この差がどの分け方で小さくなるかを、実際に比べないと決められないからです。

  1. 組 (p, q) を p 行 q 列の行列と読むと、cost は行列を左から並んだ順に掛けるときの、数どうしの掛け算の最小回数です。p 行 q 列と q 行 s 列の行列の積には、p * q * s 回の掛け算が要ります。