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) になります。
Option::is_none_orは Rust 1.82 で安定化しました。それより前はowner[job].map_or(true, |q| ...)と書いていました。