結果

問題 No.309 シャイな人たち (1)
コンテスト
ユーザー titia
提出日時 2026-06-29 06:30:17
言語 Rust
(1.94.0 + proconio + num + itertools)
コンパイル:
/usr/bin/rustc_custom
実行:
./target/release/main
結果
TLE  
実行時間 -
コード長 3,278 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 979 ms
コンパイル使用メモリ 191,580 KB
実行使用メモリ 6,528 KB
最終ジャッジ日時 2026-06-29 06:31:18
合計ジャッジ時間 11,396 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 1 TLE * 1 -- * 11
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// ChatGPTにPython→RUSTで変換してもらったもの
use std::io::{self, Read};

fn main() {
    let mut s = String::new();
    io::stdin().read_to_string(&mut s).unwrap();
    let mut it = s.split_whitespace();

    let r: usize = it.next().unwrap().parse().unwrap();
    let c: usize = it.next().unwrap().parse().unwrap();

    // Python の input() を 1 回捨てているが、
    // split_whitespace では空行は現れないため不要。

    let mut p = vec![vec![0i32; c]; r];
    for i in 0..r {
        for j in 0..c {
            p[i][j] = it.next().unwrap().parse().unwrap();
        }
    }

    // こちらの input() も不要。

    let mut s_arr = vec![vec![0i32; c]; r];
    for i in 0..r {
        for j in 0..c {
            s_arr[i][j] = it.next().unwrap().parse().unwrap();
        }
    }

    let size = 1usize << c;

    let mut dp = vec![0.0f64; size];
    dp[0] = 1.0;

    let mut ans = 0.0f64;

    for i in 0..r {
        let mut ndp = vec![0.0f64; size];

        for j in 0..size {
            let mut prob = 1.0f64;
            let mut p1 = vec![0i32; c];

            for k in 0..c {
                if (j >> k) & 1 == 1 {
                    prob *= p[i][k] as f64 / 100.0;
                    p1[k] = 4 - s_arr[i][k];
                } else {
                    prob *= (100 - p[i][k]) as f64 / 100.0;
                }
            }

            if prob == 0.0 {
                continue;
            }

            for k in 0..size {
                let prob2 = dp[k];

                if prob2 == 0.0 {
                    continue;
                }

                let mut p2 = p1.clone();
                let mut q = Vec::<usize>::new();
                let mut up = vec![false; c];

                for kk in 0..c {
                    if ((k >> kk) & 1) == 1 {
                        p2[kk] += 1;
                    }

                    if p2[kk] >= 4 {
                        up[kk] = true;
                        q.push(kk);
                    }
                }

                while let Some(x) = q.pop() {
                    if x > 0 {
                        let z = x - 1;
                        if !up[z] {
                            p2[z] += 1;
                            if p2[z] == 4 {
                                up[z] = true;
                                q.push(z);
                            }
                        }
                    }

                    if x + 1 < c {
                        let z = x + 1;
                        if !up[z] {
                            p2[z] += 1;
                            if p2[z] == 4 {
                                up[z] = true;
                                q.push(z);
                            }
                        }
                    }
                }

                let mut bi = 0usize;
                let mut count = 0usize;

                for jj in 0..c {
                    if up[jj] {
                        bi |= 1usize << jj;
                        count += 1;
                    }
                }

                let add = prob * prob2;
                ndp[bi] += add;
                ans += count as f64 * add;
            }
        }

        dp = ndp;
    }

    println!("{:.15}", ans);
}
0