#1146804 (Rust) No.174 カードゲーム（Hard）

• 問題: No.174 カードゲーム（Hard）
• ユーザー: cologne
• 提出日時: 2026-02-05 15:31:35
• 言語: Rust (1.93.0 + proconio + num + itertools)
• 結果: AC
• 実行時間: 2 ms / 2,000 ms
• コード長: 3,767 bytes
• コンパイル時間: 1,965 ms
• コンパイル使用メモリ: 210,272 KB
• 実行使用メモリ: 7,976 KB
• 最終ジャッジ日時: 2026-02-05 15:31:38
• 合計ジャッジ時間: 3,419 ms
• ジャッジサーバーID （参考情報）: judge4 / judge1

ファイルパターン	結果
other	AC * 12

ソースコード

use fio::*;

/// dp[t][c]: prob of card c popping in turn t
fn calc(n: usize, p: f64) -> Vec<Vec<f64>> {
    let mut dp = vec![vec![0f64; n]; n];

    // prob[c][i]: prob of c'th card existing in i'th position
    let mut prob = vec![vec![0f64; n]; n];
    for i in 0..n {
        prob[i][i] = 1.0;
    }
    for rem in (1..=n).rev() {
        if rem == 1 {
            for c in 0..n {
                dp[n - rem][c] = prob[c][0];
            }
        } else {
            let mut nprob = vec![vec![0f64; rem - 1]; n];
            let q = (1.0 - p) / (rem - 1) as f64;
            // i -> dp: if i == 0 { p } else { q }
            // i -> i-1: p + (i-1) * q (ignore on i=0)
            // i -> i: (rem-1-i) * q (ignore on i=rem-1)
            for c in 0..n {
                for i in 0..rem {
                    dp[n - rem][c] += prob[c][i] * if i == 0 { p } else { q };
                    if i != 0 {
                        nprob[c][i - 1] += prob[c][i] * (p + (i - 1) as f64 * q);
                    }
                    if i != rem - 1 {
                        nprob[c][i] += prob[c][i]*((rem - 1 - i) as f64 * q);
                    }
                }
            }
            prob = nprob;
        }
    }
    dp
}

fn main() {
    let [n, pa, pb] = read_tuple::<String, 3>();
    let n: usize = n.parse().unwrap();
    let (pa, pb): (f64, f64) = (pa.parse().unwrap(), pb.parse().unwrap());

    let mut a = read_vec::<f64>();
    let mut b = read_vec::<f64>();
    a.sort_by(|a, b| a.total_cmp(b));
    b.sort_by(|a, b| a.total_cmp(b));
    let pa = calc(n, pa);
    let pb = calc(n, pb);
    let mut ans = 0.0;
    for t in 0..n {
        for i in 0..n {
            for j in 0..n {
                if a[i] > b[j] {
                    ans += pa[t][i] * pb[t][j] * (a[i] + b[j]);
                }
            }
        }
    }
    println!("{:.12}", ans);
}

mod fio {
    use std::{
        cell::RefCell,
        convert::TryInto,
        fmt::Debug,
        io::{BufRead, BufWriter, StdinLock, StdoutLock, stdin, stdout},
        str::FromStr,
    };
    thread_local! {
        pub static STDIN: RefCell<StdinLock<'static>> = RefCell::new(stdin().lock());
        pub static STDOUT: RefCell<BufWriter<StdoutLock<'static>>> = RefCell::new(BufWriter::new(stdout().lock()));
    }

    #[allow(dead_code)]
    pub fn read<T: FromStr>() -> T
    where
        <T as FromStr>::Err: Debug,
    {
        read_line().parse().unwrap()
    }

    #[allow(dead_code)]
    pub fn read_vec<T: FromStr>() -> Vec<T>
    where
        <T as FromStr>::Err: Debug,
    {
        read_line()
            .split_whitespace()
            .map(|x| x.parse().unwrap())
            .collect()
    }

    #[allow(dead_code)]
    pub fn read_tuple<T, const N: usize>() -> [T; N]
    where
        T: FromStr + Debug,
        <T as FromStr>::Err: Debug,
    {
        read_vec::<T>().try_into().unwrap()
    }

    /// whitespace at the end of the line is ignored
    pub fn read_line() -> String {
        let mut s = String::new();
        STDIN.with(|cell| {
            cell.borrow_mut().read_line(&mut s).unwrap();
        });
        String::from_str(s.trim_end()).unwrap()
    }
}

#[macro_export]
macro_rules! print {
    ($($t:tt)*) => {
        fio::STDOUT.with(|cell|{
            use std::io::Write;
            write!(cell.borrow_mut(), $($t)*).unwrap()
        })};
}

#[macro_export]
macro_rules! println {
    ($($t:tt)*) => {
        fio::STDOUT.with(|cell| {
            use std::io::Write;
            writeln!(cell.borrow_mut(), $($t)*).unwrap()
        })
    };
}

#[macro_export]
macro_rules! flush {
    () => {
        fio::STDOUT.with(|cell| {
            use std::io::Write;
            cell.borrow_mut().flush().unwrap()
        });
    };
}