Namaran

Code daily. Without assist.

2026-10-05

assign.rs

fn assign(can_do: &[Vec<usize>], jobs: usize) -> Vec<Option<usize>> {
}

人 p がこなせる仕事の番号の一覧 can_do[p] と、仕事の数 jobs を受け取る assign を書いてください。1つの仕事は1人にしか割り当てず、仕事を割り当てられる人ができるだけ多くなるようにして、人ごとの仕事の番号を返します。仕事のない人は None で、人が0人なら空の Vec です。人数が最大になる割り当て方が何通りもあるときは、どれを返してもかまいません。

入力例 1

assign(&[vec![0, 1], vec![0]], 2)

出力例 1

[Some(1), Some(0)]

入力例 2

assign(&[vec![1], vec![], vec![0, 1]], 2)

出力例 2

[Some(1), None, Some(0)]

入力例 3

assign(&[], 3)

出力例 3

[]
Reference
fn augment(p: usize, can_do: &[Vec<usize>], seen: &mut [bool], owner: &mut [Option<usize>]) -> bool {
    for &job in &can_do[p] {
        if std::mem::replace(&mut seen[job], true) {
            continue;
        }
        if owner[job].is_none_or(|q| augment(q, can_do, seen, owner)) {
            owner[job] = Some(p);
            return true;
        }
    }
    false
}

fn assign(can_do: &[Vec<usize>], jobs: usize) -> Vec<Option<usize>> {
    let mut owner = vec![None; jobs];
    for p in 0..can_do.len() {
        augment(p, can_do, &mut vec![false; jobs], &mut owner);
    }
    let mut job_of = vec![None; can_do.len()];
    for (job, p) in owner.into_iter().enumerate() {
        if let Some(p) = p {
            job_of[p] = Some(job);
        }
    }
    job_of
}

参考実装は、人を1人ずつ加え、そのたびに augment で仕事を探します。空いている仕事があればそれを取ります。埋まっていれば、その持ち主に別の仕事へ移れないかを再帰で尋ね、移れた分だけ割り当てを1つずつずらします。こうして1人増やせる経路を増加路と呼び、人を加えるたびに増加路を探せば、最後には人数が最大の割り当てになります1。

早い者勝ちでは足りません。入力例1で人0が先に仕事0を取ると、人1は何も取れません。人0を仕事1へ移せば2人とも仕事に就けるので、すでに決めた割り当てを組み替える探索が要ります。

seen は、1回の探索の中で同じ仕事を2度尋ねないための印です。これが無いと、2人が互いに相手へ譲ろうとして再帰が終わりません。逆に人をまたいで使い回すと、前の人の探索で付いた印のせいで、まだ譲ってもらえるはずの持ち主に尋ねないまま諦めてしまいます。そのため人ごとに新しい &mut vec![false; jobs] を渡しています。std::mem::replace は、印を true にしながら前の値を返します。

Rust ではクロージャから自分自身を呼べないので、再帰する部分は関数 augment に分け、seen と owner を &mut で渡します。is_none_or に渡すクロージャはこの2つを可変で借用しますが、owner[job] は Option<usize> の値としてコピーされた後なので、借用はぶつかりません。最後に、仕事から人を引く owner を、人から仕事を引く job_of に裏返して返します。

掲載したのは参考実装で、唯一の正解ではありません。仕事を1つずつ加えて人を探す向きに書いても、仕事から人を引く表と人から仕事を引く表を両方持って一緒に更新しても、割り当てられる人数の最大値は同じです。

  1. 人を1人ずつ加えて増加路を探すこの方法は Kuhn の方法と呼ばれます。増加路が見つからなくなった割り当ては最大である、という Berge の定理がその正しさを支えています。