Namaran

Code daily. Without assist.

2026-10-05

kuhn.rs

fn try_assign(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| try_assign(q, can_do, seen, owner)) {
            owner[job] = Some(p);
            return true;
        }
    }
    false
}

fn main() {
    let can_do = [vec![0, 1], vec![0], vec![1, 2]];
    let mut owner = vec![None; 3];
    for p in 0..3 {
        try_assign(p, &can_do, &mut [false; 3], &mut owner);
    }
    println!("{owner:?}");
}

これは何を出力するでしょうか?

Answer

[Some(1), Some(0), Some(2)] です。

owner[job] は仕事 job を受け持つ人です。is_none_or は、None ならクロージャを呼ばずに true を返し、Some(q) のときだけクロージャに q を渡して、その結果を返します。その前の std::mem::replace は seen[job] を true にしながら前の値を返すので、1回の探索で尋ねた仕事は2度目から飛ばされます。人0は空いている仕事0を取り、owner[0] は Some(0) になります。

人1がこなせるのは仕事0だけで、そこには人0がいます。早い者勝ちなら人1は何も取れないところですが、ここでクロージャが try_assign(0, ...) を呼び、人0に別の仕事を探させます。仕事0にはこの探索で印が付いているので、人0はそれを飛ばして仕事1へ移り、owner[1] = Some(0) として true を返します。これを受けて、仕事0は人1のものになります。

人2は仕事1から試し、その持ち主の人0にまた移れないかを尋ねます。人0の候補のうち、仕事1にはこの探索で印が付いています。仕事0は人1が持っていますが、人1の候補は仕事0しかなく、それにも印が付いています。譲ってもらえなかったので人2は仕事2を取り、owner[2] は Some(2) になります。

  1. Option::is_none_or は Rust 1.82 で安定化しました。それより前は owner[job].map_or(true, |q| ...) と書いていました。