AtCoder Beginner Contest 314 E

https://atcoder.jp/contests/abc314/tasks/abc314_e

必要な残りのポイント数を状態、支払金額を値にしてDPすればよいです。
ただ、Sが0のときは注意が必要ですね。

ですが、例2でルーレット2を選んだとき(m > 0)、

なので、

となります。

// Roulettes
#![allow(non_snake_case)]


//////////////////// 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()
}


//////////////////// Roulette ////////////////////

struct Roulette {
    C: f64,
    S: Vec<usize>
}

impl Roulette {
    fn expected_value(&self, m: usize, dp: &Vec<f64>) -> f64 {
        let mut e: f64 = 0.0;
        let p: f64 = 1.0 / (self.S.len() as f64);
        let mut p0 = 0.0;
        for &s in self.S.iter() {
            if s == 0 {
                p0 += p
            }
            else {
                e += p * dp[if s > m { 0 } else { m-s }]
            }
        }
        (e + self.C) / (1.0 - p0)
    }
    
    fn read() -> Roulette {
        let v: Vec<usize> = read_vec();
        let C = v[0] as f64;
        let S: Vec<usize> = v[2..].into_iter().map(|&e| e).collect();
        Roulette { C, S }
    }
}



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

fn read_input() -> (usize, Vec<Roulette>) {
    let v: Vec<usize> = read_vec();
    let N = v[0];
    let M = v[1];
    let roulettes: Vec<Roulette> = (0..N).map(|_| Roulette::read()).collect();
    (M, roulettes)
}

fn f(M: usize, roulettes: Vec<Roulette>) -> f64 {
    let mut dp: Vec<f64> = vec![0.0; M+1];
    for m in 1..M+1 {
        dp[m] = roulettes.iter().map(|r| r.expected_value(m, &dp)).
                        min_by(|a, b| a.partial_cmp(b).unwrap()).unwrap();
    }
    dp[M]
}


//////////////////// main ////////////////////

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