Namaran

Code daily. Without assist.

2026-10-29

MinAssign.hs

minAssign :: [[Int]] -> Int

n 人に n 個の仕事を1つずつ、どの仕事も誰か1人が受け持つように割り当てます。costs !! p !! t は p 番目の人が t 番目の仕事をするときの費用です。費用の合計が最も小さくなる割り当てを選んだときの合計を返す minAssign を書いてください。n は15以下で、n 人の並べ方をすべて試すと15人では約1.3兆通りになって終わらないので、それより大幅に少ない計算で求めます。costs が空のときは0を返します。

入力例 1

minAssign [[9, 2, 7], [6, 4, 3], [5, 8, 1]]

出力例 1

9

入力例 2

minAssign [[5]]

出力例 2

5

入力例 3

minAssign []

出力例 3

0
Reference
minAssign :: [[Int]] -> Int
minAssign costs = table ! 0
 where
  n = length costs
  full = bit n - 1 :: Int
  cost = listArray ((0, 0), (n - 1, n - 1)) (concat costs) :: Array (Int, Int) Int
  table = listArray (0, full) (map best [0 .. full]) :: Array Int Int
  best used
    | used == full = 0
    | otherwise =
        minimum
          [ cost ! (popCount used, task) + table ! setBit used task
          | task <- [0 .. n - 1]
          , not (testBit used task)
          ]

仕事を割り当てる順番は人の番号順に固定できます。0番目の人から順に仕事を選んでいけば、すべての割り当てをちょうど1回ずつ作れるからです。こうすると、すでに何個の仕事を割り当てたかが、次に選ぶ人の番号そのものになります。状態として覚えるのは「どの仕事が割り当て済みか」の集合 used だけで、次の人は popCount used 番目の人です。誰がどの仕事を取ったかの内訳は、残りの最小費用に影響しません。

table ! used は、used の仕事が割り当て済みのとき、残りの人に残りの仕事を割り当てる最小費用です。次の人が空いている仕事 task を取ると、その費用に table ! setBit used task を足した値になり、その最小値が table ! used です。全部が割り当て済みなら0で、答えは何も割り当てていない table ! 0 です。table は自分自身を参照する配列で、要素は遅延評価で必要になったときに計算されます。状態は2n通り、1つの状態で調べる仕事は n 個なので、15人でも約50万回の計算で済みます。

入力例1では、0番目の人が仕事1(費用2)、1番目の人が仕事0(費用6)、2番目の人が仕事2(費用1)を受け持つ合計9が最小です。n が0のときは full が0で、table ! 0 は「全部が割り当て済み」の0になります。

掲載したのは参考実装で、唯一の正解ではありません。配列の代わりに Data.Map でメモ化する書き方や、集合を小さい順に並べて foldl で表を埋めていく書き方もあります。