2026-10-30
valid_order.rs
fn is_valid_order(order: &[usize], deps: &[(usize, usize)]) -> bool {
}
order は作業 0 から order.len() - 1 までを1回ずつ並べた順番で、deps の組 (a, b) は「作業 a は作業 b より前にする」という条件です。order がすべての条件を守っていれば true、1つでも破っていれば false を返す is_valid_order を書いてください。deps が空なら true です。
入力例 1
is_valid_order(&[2, 0, 1], &[(0, 1), (2, 1)])
出力例 1
true
入力例 2
is_valid_order(&[1, 0, 2], &[(0, 1)])
出力例 2
false
入力例 3
is_valid_order(&[0, 1], &[])
出力例 3
true
Reference
fn is_valid_order(order: &[usize], deps: &[(usize, usize)]) -> bool {
let mut pos = vec![0; order.len()];
for (i, &task) in order.iter().enumerate() {
pos[task] = i;
}
deps.iter().all(|&(before, after)| pos[before] < pos[after])
}
条件 (a, b) を確かめるには、a と b が order の何番目にあるかを知る必要があります。そのたびに order を探すと、条件1つごとに並び全体をなめることになるので、先に pos[task] に作業 task の位置を書いた表を作ります。order は各作業を1回ずつ含むので、表の要素はちょうど1回ずつ埋まります。
表ができれば、条件ごとの確認は pos[before] < pos[after] の比較1回で済みます。all は1つでも false が出た時点で止まり、deps が空なら一度も比べずに true を返すので、空の場合を別に書く必要はありません。
掲載したのは参考実装で、唯一の正解ではありません。order.iter().position で毎回位置を探す書き方でも結果は同じで、作業の数が少なければそれで十分です。