PAST #15 第15回 アルゴリズム実技検定(過去問)

• G - N-SAT https://atcoder.jp/contests/past15-open/tasks/past202306_g
  • 提出: https://atcoder.jp/contests/past15-open/submissions/48431538
  • (2^N)MN でも N <= 15 で M <= 100 で 49,152,000 なので間に合う
  • ビット全探索ですべての組み合わせに対して M の条件をすべて試せばいい

use proconio::{input, marker::Usize1};

fn main() {
    input! {
        n: usize,
        m: usize,
    };
    let mut abs = vec![];
    for _ in 0..m {
        input! {
            k: usize,
            ab: [(Usize1, usize); k],
        }
        abs.push(ab);
    }

    for bits in 0..1 << n {
        let x = (0..n).map(|i| (bits >> i) & 1).collect::<Vec<usize>>();
        if abs
            .iter()
            .all(|ab| ab.iter().copied().any(|(a, b)| x[a] == b))
        {
            println!("Yes");
            return;
        }
    }
    println!("No");
}

今日のコミット。

• rust-atcoder 1 commit
  • past15-open g
• rust-examples 1 commit
  • Add wrap fn
• serde-firestore-value 1 commit
  • Fix clippy warnings
• genpi 1 commit
  • Fix clippy warnings