・0 pv・2 min read
RustとAtCoderを勉強する(typical90_p)
はじめに
AtCoder の問題を Rust で解いていきます。AtCoder も Rust も初心者ですが、温かい目で成長を見守っていただけるとありがたいです。
今回は、競プロ典型90問の016 - Minimum Coins（★3）を解きました。
提出コード
use itertools::Itertools;
use proconio::{fastout, input};
#[fastout]
fn main() {
input! {
n: usize,
mut abc: [usize; 3],
}
abc.sort_unstable();
abc.reverse();
let (a, b, c) = abc.into_iter().collect_tuple().unwrap();
let mut ans = 10000;
for i in 0..=(n / a) {
for j in 0..=((n - a * i) / b) {
let sum = a * i + b * j;
if (n - sum) % c == 0 {
ans = ans.min(i + j + (n - sum) / c);
}
}
}
println!("{}", ans);
}解説
A, B, C 円の硬貨を使って N 円ぴったり支払う時、最も少ない枚数を求める問題です。また、「合計 9999 枚以下の硬貨でちょうど N 円を支払うことができる」という制約があります。全探索を行うと時間切れになるので、A, B についてのみ探索を行い、C は計算で求めるようにすると間に合います。
まとめ
競プロ用ツール
cargo-compete を使用しているのですが、提出コードをローカルでテストすると毎回 TLE となってしまいました。問題ページにコピペして提出すると問題なく（しかも結構時間に余裕あり）通りました。何が問題だったのか気になります。