Namaran

Code daily. Without assist.

2026-10-05

matching.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 seen[job] {
            continue;
        }
        seen[job] = true;
        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]];
    let mut owner = [None; 2];
    let mut seen = [false; 2];
    let n = (0..2).filter(|&p| try_assign(p, &can_do, &mut seen, &mut owner)).count();
    println!("{n}");
}

main は、人ごとにこなせる仕事の一覧 can_do から、別々の仕事を割り当てられる最大の人数を数えるつもりのコードです。can_do は、人0が仕事0と1、人1が仕事0だけで、引数も標準入力も使いません。いまは 1 が出ます。人0を仕事1に、人1を仕事0に割り当てられるので、本来は 2 が出るはずです。

Answer

Wrong

    let mut seen = [false; 2];
    let n = (0..2).filter(|&p| try_assign(p, &can_do, &mut seen, &mut owner)).count();

seen は、1回の探索の中で尋ね済みの仕事に付ける印ですが、main で1回だけ作られ、2人分の探索で共有されています。人0の探索で仕事0を取ったときに付いた seen[0] は、そのまま残ります。

人1の探索は仕事0から始まりますが、seen[0] が true なので尋ね済みとして飛ばされます。持ち主の人0に仕事1へ移ってもらう道は試されないまま false が返り、数えられるのは人0だけの 1 です。

Right

    let n = (0..2).filter(|&p| try_assign(p, &can_do, &mut [false; 2], &mut owner)).count();

人ごとに新しい [false; 2] を渡せば、印は1人分の探索の中でだけ効きます。同じ探索で同じ仕事を2度尋ねないという本来の役目は残り、人1の探索は仕事0の持ち主の人0に尋ねます。人0が仕事1へ移り、人1が仕事0を取って、2 になります1。

  1. 印を消すのは探索が成功したときだけにする、という高速化もあります。失敗した探索で付いた印は、割り当てが変わらない限り、同じ仕事を何度尋ねても失敗するという情報だからです。このコードの誤りは、人0の探索が成功して割り当てが変わった後も印を残したことです。