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