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 で表を埋めていく書き方もあります。