Namaran

Code daily. Without assist.

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 が失敗することもありません。