結果

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

ソースコード

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();

    // 区切り文字入力を読み飛ばす

    let mut p = vec![vec![0.0_f64; c]; r];
    for i in 0..r {
        for j in 0..c {
            let v: f64 = it.next().unwrap().parse::<f64>().unwrap();
            p[i][j] = v;
        }
    }

    // 区切り文字入力を読み飛ばす
    
    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().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 >> k) & 1 == 1 {
                    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 = 0i32;

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

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

                for kk in 0..c {
                    if ((up >> kk) & 1) == 1 {
                        continue;
                    }

                    let mut point = p2[kk];

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

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

                for kk in (0..c).rev() {
                    if ((up >> kk) & 1) == 1 {
                        continue;
                    }

                    let mut point = p2[kk];

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

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

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

        dp = ndp;
    }

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