blog.bouzuya.net

2023-02-01 PAST #11 の H を解いた / L チカ

PAST #11 第11回 アルゴリズム実技検定 過去問 の H を解いた。

  • H - 2つのナップサック https://atcoder.jp/contests/past202206-open/tasks/past202206_h
    • 提出: https://atcoder.jp/contests/past202206-open/submissions/38527462
    • いわゆるナップサック問題でナップサックが 2 つあったら……という問題
    • A も B も小さいので素朴な全探索っぽい走査でなんとかなる
    • dp[i][j][k] := i 番目まで見て 1 つ目のナップサックの重さが j で 2 つ目のナップサックの重さが k のときの価値の最大値 とおく
    • それぞれのお菓子について 1 つ目に入れるか 2 つ目に入れるかどちらにも入れないかをナップサックの重さの組み合わせすべてに対して試せば良い
    • 答えは dp[n] の j, k をすべて試して最大を取れば良い
use proconio::input;

macro_rules! chmax {
    ($max_v: expr, $v: expr) => {
        if $v > $max_v {
            $max_v = $v;
            true
        } else {
            false
        }
    };
}

fn main() {
    input! {
        n: usize,
        a: usize,
        b: usize,
        wv: [(usize, usize); n],
    };

    let mut dp = vec![vec![vec![0_usize; b + 1]; a + 1]; n + 1];
    for (i, (w, v)) in wv.iter().copied().enumerate() {
        for j in 0..=a {
            for k in 0..=b {
                if j + w <= a {
                    chmax!(dp[i + 1][j + w][k], dp[i][j][k] + v);
                }
                if k + w <= b {
                    chmax!(dp[i + 1][j][k + w], dp[i][j][k] + v);
                }
                chmax!(dp[i + 1][j][k], dp[i][j][k]);
            }
        }
    }

    let mut max = 0_usize;
    for j in 0..=a {
        for k in 0..=b {
            chmax!(max, dp[n][j][k]);
        }
    }

    let ans = max;
    println!("{}", ans);
}

Arduino Micro を Rust で L チカした。

unsafe { write_volatile(DDRC, 0b10000000) } とかしている。

前に触ったときよりは crates:avrd で DDRC のような定数を使えるようになっているし、なぜか最新版が公開されていないのでリポジトリを見ているけど crates:avr_delay で sleep もできた。

もうすこし調べてから書く。

今日のコミット。