結果

問題 No.144 エラトステネスのざる
ユーザー Ryota BannaiRyota Bannai
提出日時 2022-10-02 00:38:44
言語 Rust
(1.77.0)
結果
AC  
実行時間 116 ms / 2,000 ms
コード長 2,979 bytes
コンパイル時間 3,343 ms
コンパイル使用メモリ 152,500 KB
実行使用メモリ 6,120 KB
最終ジャッジ日時 2023-08-25 20:46:18
合計ジャッジ時間 5,485 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 1 ms
4,380 KB
testcase_06 AC 1 ms
4,380 KB
testcase_07 AC 1 ms
4,380 KB
testcase_08 AC 1 ms
4,376 KB
testcase_09 AC 1 ms
4,380 KB
testcase_10 AC 1 ms
4,376 KB
testcase_11 AC 1 ms
4,376 KB
testcase_12 AC 1 ms
4,380 KB
testcase_13 AC 93 ms
6,120 KB
testcase_14 AC 104 ms
6,052 KB
testcase_15 AC 116 ms
6,116 KB
testcase_16 AC 108 ms
6,056 KB
testcase_17 AC 109 ms
6,112 KB
testcase_18 AC 109 ms
6,112 KB
testcase_19 AC 78 ms
6,112 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

pub use __cargo_equip::prelude::*;

/**
 * @cpg_dirspec eratosthenes_zaru
 *
 * cpg run -p src/bin/dp/probability/eratosthenes_zaru.rs
 */
// use proconio::{fastout, input, marker::Chars};
// use std::cmp::{max, min};
// use superslice::Ext;
// use ac_library_rs::modint::ModInt998244353 as Mint;
// use superslice::{self, Ext};
// use derive_new::new;
// use indexmap::indexmap;
// use std::collections::{BTreeMap, BTreeSet};
// type Map = BTreeMap<String, usize>;
// type Set = BTreeSet<(usize, usize)>;
// use easy_ext::ext;
// use std::collections::{BinaryHeap, VecDeque};
use collection::utils::read;

/**
 * 確率DP HSI
 *
 * https://yukicoder.me/problems/no/144
 *
 * tags: #DP #確率DP
 *
 * 2つリストがある. これらをA、Bをする.
 * Aは自然数x {x|2<=x<=N} であり、このリストから、最小mi を選んでBに移すことを考える.
 * この時、確率p でmi の倍数をAから削除する.
 * Aが空{} になるまで、移動すること操作を行うとき、Bの要素数の期待値を求めよ.
 *
 *
 * 「Bの要素数の期待値」について何を求めるか？
 * -> 各要素がB に移される期待値の総和
 * -> 各要素は独立に計算できて、それぞれカウントは１だから、各要素がB に移される時の確率を求めれば良い！（ei=1*pi=pi {pi: i∈N}）
 * -> 倍数が削除されるというのは、削除される p の余事象（1-p）
 * -> 約数全てが削除されないなら、自身が最小となる時にB へ移される
 *
 * 6 が B に移される
 * =2,3 の倍数が削除されない (1-p)^2 2:= １以上約数 - 1(=自分)
 *
*/

// #[fastout]
fn main() {
    let a = read::<f64>();
    let (n, p) = (a[0] as usize, a[1]);

    let mut div = vec![0; n + 1];
    let mut e = 0.;
    for k in 2..=n {
        for m in (k..=n).step_by(k) {
            div[m] += 1;
        }
        e += (1. - p).powf((div[k] - 1) as f64); // 約数が移動されない確率で良い
    }

    println!("{:.7}", e);
}

// The following code was expanded by `cargo-equip`.

///  # Bundled libraries
/// 
///  - `collection 0.1.0 (path+████████████████████████████████████████████████████████████████████████)` published in **missing** licensed under **missing** as `crate::__cargo_equip::crates::collection`
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
    pub(crate) mod crates {
        pub mod collection {pub mod utils{use std::io;pub fn read<T:std::str::FromStr>()->Vec<T>{let mut buf=String::new();io::stdin().read_line(&mut buf).unwrap();buf.trim().split(' ').flat_map(str::parse).collect()}}}
    }

    pub(crate) mod macros {
        pub mod collection {}
    }

    pub(crate) mod prelude {pub use crate::__cargo_equip::crates::*;}

    mod preludes {
        pub mod collection {}
    }
}
0