Atcoder ABS ABC087B Coins

こんにちは、ナナオです。

前回に引き続き競プロを実施していきたいと思います。

今回の問題は以下です。

実装

以下のような実装を行いました。制約が緩いので全探索ですね。

use proconio::input;

fn main() {
    input! {
        a: u16,
        b: u16,
        c: u16,
        x: u16,
    };
    let mut cnt = 0;
    for i in 0..a + 1 {
        for j in 0..b + 1 {
            for k in 0..c + 1 {
                if 500 * i + 100 * j + 50 * k == x {
                    cnt += 1;
                }
            }
        }
    }
    println!("{}", cnt);
}

これで通りました。

ちょっと物足りなかったので、AIと壁打ちしてもうちょっと早い方法にしました。

考え方としては以下の通りです。

「余り物」計算作戦（計算量：O(AB)）

500円玉と100円玉の枚数を決めた時点で、「あと何円足りないか」は計算で出せます。

その足りない分を50円玉でピッタリ埋められるかチェックします。

手順は以下の通りです。

500円玉を $i$ 枚、100円玉を $j$ 枚選ぶ（ここはループ）。
残りの金額を計算する： Rem = X - (500i + 100j)
判定： Rem が 0 以上か？（払いすぎてないか）

Rem が 50円玉の合計（50 \ C）以下か？（足りるか）
Rem は 50円で割り切れるか？（ピッタリいけるか）

これだけで、50円玉の枚数を1枚ずつ試すループ（レバーC）を丸ごとカットできます！

ということでコードは以下の通りです。

use proconio::input;

fn main() {
    input! {
        a: i16,
        b: i16,
        c: i16,
        x: i16,
    };
    let mut cnt = 0;
    for i in 0..=a {
        for j in 0..=b {
            let rem = x - (500 * i + 100 * j);
            if rem >= 0 && rem <= 50 * c {
                cnt += 1;
            }
        }
    }
    println!("{}", cnt);
}

地味にfor文のあたりも0..=aと少し記法を変えています。こんな書き方があるんですね。便利。

ということで今回はこれで👍

実装#

実装