Ccmmutty logo
Commutty IT
・2 min read

RustとAtCoderを勉強する(typical90_p)

AtCoderRust
https://cdn.magicode.io/media/notebox/blob_EIznrdW

はじめに

AtCoder の問題を Rust で解いていきます。AtCoder も Rust も初心者ですが、温かい目で成長を見守っていただけるとありがたいです。
今回は、競プロ典型90問の016 - Minimum Coins（★3）を解きました。

提出コード

rust
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 となってしまいました。問題ページにコピペして提出すると問題なく（しかも結構時間に余裕あり）通りました。何が問題だったのか気になります。

Discussion

コメントにはログインが必要です。