AtCoder Beginner Contest 342 F

https://atcoder.jp/contests/abc342/tasks/abc342_f

まず最終的にyがいくつになるかの確率を求めて、自分の勝つ確率を求めます。そこでやめたときの勝つ確率と、サイコロを振ったときの勝つ確率を求めます。

// Black Jack
#![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 ////////////////////

fn read_input() -> (usize, usize, usize) {
    let v: Vec<usize> = read_vec();
    let (N, L, D) = (v[0], v[1], v[2]);
    (N, L, D)
}

fn calc_dealder(L: usize, D: usize) -> Vec<f64> {
    let mut acc: Vec<f64> = vec![0.0; L+D+1];
    acc[1] = 1.0;
    for i in 1..L+1 {
        let first = if i < D { 0 } else { i - D };
        acc[i+1] = acc[i] + (acc[i] - acc[first]) / (D as f64)
    }
    for i in L+1..L+D {
        let first = if i < D { 0 } else { i - D };
        acc[i+1] = acc[i] + (acc[L] - acc[first]) / (D as f64)
    }
    for i in L+1..L+D+1 {
        acc[i] -= acc[L]
    }
    for i in 1..L+1 {
        acc[i] = 0.0
    }
    acc
}

fn F(N: usize, L: usize, D: usize) -> f64 {
    let acc_dealer = calc_dealder(L, D);
    let accumulate = |first, last| -> f64 {
        if first > L+D {
            0.0
        }
        else {
            acc_dealer[min(last, L+D)] - acc_dealer[first]
        }
    };
    
    let mut acc_win: Vec<f64> = vec![0.0; N+2];
    for x in (0..N+1).rev() {
        // やめた場合
        let p1 = 1.0 - accumulate(x, N+1);
        // 続けた場合
        let p2 = (acc_win[x+1] - acc_win[min(N+1, x+D+1)]) / (D as f64);
        acc_win[x] = acc_win[x+1] + f64::max(p1, p2);
    }
    acc_win[0] - acc_win[1]
}

fn main() {
    let (N, L, D) = read_input();
    println!("{}", F(N, L, D))
}