AtCoder Beginner Contest 317 D

https://atcoder.jp/contests/abc317/tasks/abc317_d

単なるDPですね。上の選挙区から処理して、獲得した議席の数を状態とします。ナップザック問題に似ていますね。

// President
#![allow(non_snake_case)]

use std::cmp::min;


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// process ////////////////////

type State = (i64, i64, usize);

// 当選者の数が増えるときに何人の有権者を鞍替えさせなければならないか
fn calc_swapping_voters(state: &State) -> i64 {
    if state.0 > state.1 {
        0
    }
    else {
        (state.1 - state.0 + 1) / 2
    }
}

fn read_state() -> State {
    let v = read_vec();
    (v[0], v[1], v[2] as usize)
}

fn read_input() -> Vec<State> {
    let N: usize = read();
    (0..N).map(|_| read_state()).collect::<Vec<_>>()
}

fn initialize_dp(states: &Vec<State>) -> Vec<i64> {
    let total = states.iter().map(|v| v.2).sum::<usize>();
    let mut dp = vec![10i64.pow(18); total+1];
    dp[0] = 0;
    dp
}

fn update_dp(dp: Vec<i64>, state: State) -> Vec<i64> {
    let mut new_dp: Vec<i64> = (0..dp.len()).map(|_| 10i64.pow(18)).collect();
    for i in 0..dp.len() {
        // 当選者が増える場合
        let j = i + state.2;    // 新しい当選者の数
        if j < dp.len() {
            new_dp[j] = min(new_dp[j], dp[i] + calc_swapping_voters(&state))
        }
        
        // 当選者が増えない場合
        if state.0 < state.1 {
            new_dp[i] = min(new_dp[i], dp[i])
        }
    }
    new_dp
}

fn f(states: Vec<State>) -> i64 {
    let mut dp = initialize_dp(&states);
    let half = dp.len() / 2;
    for state in states.into_iter() {
        dp = update_dp(dp, state)
    }
    dp[half..].iter().map(|&v| v).min().unwrap()
}

fn main() {
    let states = read_input();
    println!("{}", f(states))
}