Namaran

Code daily. Without assist.

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 を返してもかまいません。