3 Team Division の解説

はじめに、bの総和 % 3が0じゃなかったらどうやっても全チームを同じ強さにできるはずがないので0を出力する。

dp[i][j][k] := i番目までをみて、team0の強さ = j, team1の強さ = kの時の入れ替える必要がある最小値

n番目までみた時にはteam0, team1の強さが決まっていればteam2の強さも自動的に決まる。

fn main() {
    input! {
        n: usize,
        ab: [(Usize1, usize); n]
    }
    let bsum = ab.iter().map(|&e| e.1).sum::<usize>();
    if bsum % 3 != 0 {
        return println!("-1");
    }
    let target = bsum / 3;
    let mut dp = vec![vec![vec![usize::MAX; target + 1]; target + 1]; n + 1];
    dp[0][0][0] = 0;

    for i in 0..n {
        for j in 0..=target {
            for k in 0..=target {
                if dp[i][j][k] == usize::MAX {
                    continue;
                }
                let now = dp[i][j][k];
                let (a, b) = ab[i];
                if j + b <= target {
                    dp[i + 1][j + b][k].chmin(now + if a == 0 { 0 } else { 1 });
                }
                if k + b <= target {
                    dp[i + 1][j][k + b].chmin(now + if a == 1 { 0 } else { 1 });
                }
                dp[i + 1][j][k].chmin(now + if a == 2 { 0 } else { 1 });
            }
        }
    }
    let ans = dp[n][target][target];
    if ans == usize::MAX {
        return println!("-1");
    }
    println!("{}", ans);
}