2026-10-04
version_vector.rs
use std::collections::BTreeMap;
fn dominates(a: &BTreeMap<char, u32>, b: &BTreeMap<char, u32>) -> bool {
}
各レプリカから受け取った更新の回数を、レプリカ名をキーにした BTreeMap で持っています。a が b の知っている更新をすべて取り込んでいるか、つまりどのレプリカについても a の回数が b の回数以上かを返す dominates を書いてください。表に無いレプリカの回数は 0 とみなします。b が空なら true です。
入力例 1
dominates(&BTreeMap::from([('a', 3), ('b', 1)]), &BTreeMap::from([('a', 2)]))
出力例 1
true
入力例 2
dominates(&BTreeMap::from([('a', 3)]), &BTreeMap::from([('a', 2), ('b', 1)]))
出力例 2
false
入力例 3
dominates(&BTreeMap::new(), &BTreeMap::new())
出力例 3
true
Reference
fn dominates(a: &BTreeMap<char, u32>, b: &BTreeMap<char, u32>) -> bool {
b.iter().all(|(k, &n)| a.get(k).copied().unwrap_or(0) >= n)
}
調べるのは b に載っているレプリカだけで足ります。a にしか無いレプリカは b 側の回数が 0 なので、a の回数がいくつでも条件を満たすからです。参考実装は b の各項目について a の回数を引き、all ですべてが b の回数以上かを確かめます。b が空なら、all は調べる項目が無いので true を返します。
a に無いレプリカでは a.get(k) が None になるので、unwrap_or(0) で 0 回として比べます。入力例2では 'b' が a に無く、0 >= 1 が成り立たないので false です。この判定が true なら、レプリカごとに大きい方の回数を残す統合で a に b を取り込んでも何も変わらないので、統合を省けます。
掲載したのは参考実装で、唯一の正解ではありません。for で回し、足りない項目を見つけた時点で false を返してもかまいません。