blog.bouzuya.net

2023-04-27 PAST #1 I を解いた

  • PAST #1 I - 部品調達 (第一回 アルゴリズム実技検定 I 問題) https://atcoder.jp/contests/past201912-open/tasks/past201912_i
    • https://atcoder.jp/contests/past201912-open/submissions/40981119
    • bitDP
    • 部品の種類 N は N <= 10 と小さいので部品の入手状況は 2^10 個で表現できる
    • dp[i][j] := i 番目までのセットで j の部品の入手状況のときの最小の金額 とおく
    • dp[0][0] を 0 に、それ以外の初期値を INF にする
    • 1 セットずつ買う場合・買わない場合の遷移を、すべての部品の入手状況ごとに試す
    • 答えは dp[M][(1 << N) - 1] にある
    • INF のときは忘れずに -1 にする
use proconio::{input, marker::Chars};

macro_rules! chmin {
    ($min_v: expr, $v: expr) => {
        if $v < $min_v {
            $min_v = $v;
            true
        } else {
            false
        }
    };
}

fn main() {
    input! {
        n: usize,
        m: usize,
        sc: [(Chars, usize); m],
    }
    let mut tc = vec![];
    for (s, c) in sc {
        let mut t = 0_usize;
        for i in 0..n {
            if s[i] == 'Y' {
                t |= 1 << (n - i - 1);
            }
        }
        tc.push((t, c));
    }

    let inf = 1_usize << 60;
    let mut dp = vec![vec![inf; 1 << n]; m + 1];
    dp[0][0] = 0_usize;
    for (i, (t, c)) in tc.iter().copied().enumerate() {
        for bits in 0..1 << n {
            chmin!(dp[i + 1][bits], dp[i][bits]);
            chmin!(dp[i + 1][bits | t], dp[i][bits] + c);
        }
    }
    let ans = dp[m][(1 << n) - 1];
    println!("{}", if ans == inf { -1 } else { ans as i64 });
}

『介護の現場と業界のしくみ』にざっと目を通した。

Hades 。剣のアーサーの態でクリア。 7 周目。難易度を上げそびれた。

今日のコミット。