結果

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

ソースコード

diff #
raw source code 

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() に対応する空行は split_whitespace() では無視される
    let mut p = vec![vec![0.0_f64; c]; r];
    for i in 0..r {
        for j in 0..c {
            p[i][j] = it.next().unwrap().parse::<f64>().unwrap();
        }
    }

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

    let size = 1usize << c;
    let mut dp = vec![0.0_f64; size];
    dp[0] = 1.0;

    let mut ans = 0.0_f64;

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

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

            for k in 0..c {
                if (j & (1usize << k)) != 0 {
                    prob *= p[i][k] / 100.0;
                    p1[k] = 4 - s_arr[i][k];
                } else {
                    prob *= (100.0 - p[i][k]) / 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 up = 0usize;
                let mut count = 0_i32;

                for kk in 0..c {
                    if (j & (1usize << kk)) == 0 {
                        continue;
                    }

                    if (k & (1usize << kk)) != 0 {
                        p2[kk] += 1;
                    }

                    if p2[kk] >= 4 {
                        up |= 1usize << kk;
                        count += 1;
                    }
                }

                for kk in 0..c {
                    if (j & (1usize << kk)) == 0 {
                        continue;
                    }

                    if (up & (1usize << kk)) != 0 {
                        continue;
                    }

                    let mut point = p2[kk];

                    if kk > 0 && (up & (1usize << (kk - 1))) != 0 {
                        point += 1;
                    }
                    if kk + 1 < c && (up & (1usize << (kk + 1))) != 0 {
                        point += 1;
                    }

                    if point >= 4 {
                        up |= 1usize << kk;
                        count += 1;
                    }
                }

                for kk in (0..c).rev() {
                    if (j & (1usize << kk)) == 0 {
                        continue;
                    }

                    if (up & (1usize << kk)) != 0 {
                        continue;
                    }

                    let mut point = p2[kk];

                    if kk > 0 && (up & (1usize << (kk - 1))) != 0 {
                        point += 1;
                    }
                    if kk + 1 < c && (up & (1usize << (kk + 1))) != 0 {
                        point += 1;
                    }

                    if point >= 4 {
                        up |= 1usize << kk;
                        count += 1;
                    }
                }

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

        dp = ndp;
    }

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