2026-10-11
assignment.rs
fn min_assignment(cost: &[Vec<u32>]) -> u32 {
}
cost[i][j] が人 i に仕事 j を任せる費用を表す n × n の表を受け取り、全員にちょうど1件ずつ仕事を割り当てたときの費用の合計の最小値を返す min_assignment を書いてください。n は0以上16以下で、n が 0 のときは 0 を返します。
入力例 1
min_assignment(&[vec![4, 1], vec![2, 3]])
出力例 1
3
入力例 2
min_assignment(&[vec![1, 2, 3], vec![2, 4, 6], vec![3, 6, 9]])
出力例 2
10
入力例 3
min_assignment(&[])
出力例 3
0
Reference
fn min_assignment(cost: &[Vec<u32>]) -> u32 {
let n = cost.len();
// best[mask]: cheapest way to give the jobs in `mask` to workers 0..mask.count_ones()
let mut best = vec![u32::MAX; 1 << n];
best[0] = 0;
for mask in 0..1usize << n {
let worker = mask.count_ones() as usize;
if worker == n {
continue;
}
for job in (0..n).filter(|&j| mask & (1 << j) == 0) {
let next = mask | 1 << job;
best[next] = best[next].min(best[mask] + cost[worker][job]);
}
}
best[(1 << n) - 1]
}
人に 0 から順に仕事を割り当てると決めておけば、割り当て済みの仕事の集合 mask だけで状態が決まります。割り当てを終えた人数は mask の要素数 mask.count_ones() に等しく、次に仕事を受け取るのはその番号の人だからです。best[mask] を「mask の仕事を人 0 から順に割り当てたときの最小費用」とし、まだ誰にも渡していない仕事 job を次の人に渡して best[mask | 1 << job] を更新します。mask | 1 << job は mask より大きいので、mask を小さい順に回せば、使う時点で best[mask] は確定しています。
人の番号も状態に入れて best[i][mask] と書きたくなりますが、i は mask から決まるので、表が n 倍に大きくなるだけです。順列を全部試すと n! 通り、n = 16 なら約 2 × 1013 通りですが、このDPは 2n 個の集合それぞれで最大 n 件の仕事を見るだけなので、約100万回の更新で済みます。
掲載したのは参考実装で、唯一の正解ではありません。割り当て済みの人の集合を状態にして、仕事の側を 0 から順に決めても同じ値が求まります。