アルゴリズムと数学 026

https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_z

N種類だったとして最初に1種類目が出るまで1回、次の種類が出る確率は(N-1)/Nなので、次の種類が出るまでの回数の期待値はN/(N-1)、その次の種類が出る確率は(N-2)/Nなので、次の種類が出るまでの回数の期待値はN/(N-2)、などとなり、全種類が出るまでの回数の期待値は、

$1 + \frac{N}{N-1} + \frac{N}{N-2} + \dots + N$

となります。

// Coin Gacha
#![allow(non_snake_case)]

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 f(N: i32) -> f64 {
    (1..(N+1)).map(|n| (N as f64) / (n as f64)).sum::<f64>()
}

fn main() {
    let N: i32 = read();
    println!("{}", f(N))
}