Namaran

Code daily. Without assist.

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 から順に決めても同じ値が求まります。