2026-11-06
balance.rs
fn min_diff(w: &[u32]) -> u32 {
}
荷物の重さの並び w を受け取り、すべての荷物を2つのグループに分けたときの、グループごとの重さの合計の差の最小値を返す min_diff を書いてください。どちらかのグループが空になってもかまいません。荷物は20個以下で、1つもなければ0を返します。
入力例 1
min_diff(&[3, 1, 4, 2, 2])
出力例 1
0
入力例 2
min_diff(&[10, 3])
出力例 2
7
入力例 3
min_diff(&[])
出力例 3
0
Reference
Reference
fn min_diff(w: &[u32]) -> u32 {
let total: u32 = w.iter().sum();
(0..1u32 << w.len())
.map(|mask| {
let s: u32 =
w.iter().enumerate().filter(|&(i, _)| mask >> i & 1 == 1).map(|(_, x)| x).sum();
total.abs_diff(2 * s)
})
.min()
.unwrap()
}
fn main() {
println!("{}", min_diff(&[3, 1, 4, 2, 2]));
println!("{}", min_diff(&[10, 3]));
荷物が n 個なら、それぞれを片方のグループに入れるかどうかで分け方は2n 通りあり、0以上2n 未満の整数 mask の i ビット目を「i 番目の荷物を入れる」と読めば、1つの整数で1つの分け方を表せます。mask のグループの重さを s とすると、もう一方のグループには残りがすべて入るので、その重さは全体の和 total から s を引いた値です。2つのグループの差 (total - s) と s の差は、total と 2 * s の差に等しいので、もう一方のグループの和を数え直す必要はありません。u32 の引き算は負になると panic するので、abs_diff で符号を気にせず差を取っています。これは参考実装で、唯一の正解ではありません。
入力例1は全体が12で、3 + 1 + 2 の6を選ぶ mask で 12.abs_diff(12) が0になります。入力例2は、10と3を別のグループにしたときの7が最小です。入力例3では w.len() が0なので 1u32 << 0 は1で、mask は0の1回だけ回り、空のグループどうしの差0を返します。範囲が空にならないので、min() の結果は必ず Some で、unwrap() は panic しません。