2026-08-26
min_split.rs
fn min_split(w: &[u32]) -> u32 {
}
重さを並べた w の要素を2つの組に分けるとき、2つの組の重さの合計の差として取りうる最小の値を返す min_split を書いてください。片方の組が空になる分け方も含め、すべての分け方を考えます。w が空なら0を返します。w の要素は20個以下とします。
入力例 1
min_split(&[3, 1, 4, 2])
出力例 1
0
入力例 2
min_split(&[5, 8])
出力例 2
3
入力例 3
min_split(&[])
出力例 3
0
Reference
Reference
fn min_split(w: &[u32]) -> u32 {
let total: u32 = w.iter().sum();
(0..1u32 << w.len())
.map(|mask| {
let s: u32 = (0..w.len())
.filter(|i| {
mask >> i & 1 == 1
})
.map(|i| w[i])
.sum();
s.abs_diff(total - s)
})
.min()
要素が n 個なら、各要素をどちらの組に入れるかで2の n 乗通りの分け方があり、0..1u32 << w.len() の各 mask がそれぞれ1通りを表します。mask の i ビット目が1なら w[i] を一方の組に入れ、その組の合計を s とします。もう一方の組は、選ばなかった要素をすべて集めたものなので、その合計は全体の合計 total から s を引けば求まります。掲載したのは参考実装で、唯一の正解ではありません。
2つの組の差は s.abs_diff(total - s) で求めます。u32 は負の値を持てないので、s - (total - s) と引くと、s の側が小さいときにデバッグビルドではパニックします。abs_diff は大きいほうから小さいほうを引くので、この心配がありません。s は total の一部の和なので、total - s が負になることもありません。
入力例 1 では、{3, 2} と {1, 4} がどちらも合計5になり、差は0です。入力例 3 の空の w では 1u32 << 0 が1なので、mask は0の1通りだけです。何も選ばない組と空の組に分けたことになり、差0が最小値として残ります。mask は必ず1つ以上あるので、min が None を返して unwrap が失敗することもありません。