Atcoder ABS ABC085C Otoshidama

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

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

今回の問題は以下です。

実装

まずは愚直に実装しました。

はい、全探索ですね。

use proconio::input;

fn main() {
    input! {
        n: u32,
        y: u32,
    }
    for i in 0..=n {
        for j in 0..=n {
            for k in 0..=n {
                if i + j + k == n && 10000 * i + 5000 * j + 1000 * k == y {
                    println!("{} {} {}", i, j, k);
                    return;
                }
            }
        }
    }
    println!("-1 -1 -1");
}

これでも一応一部のテストケースでは通るは通るんですが、nが最大値の2000だった場合、2000^3で実に80億通りも実行しなきゃならないですね。

そうなると実行時間に間に合いません。

というわけで最適化する必要があります。

で、どう最適化するかというところなんですが、、、AIと壁打ちします。

まずは最後のループを消すという方法を試してみます。

これは、つまり10枚のお札があるときに

10000円札が 2枚
5000円札が 3枚

だとわかったら、残りの1000円札は必然的に5枚に決まる、という特徴を活かせば実装できます。

これだけで最大80億のループが4000万にまで減ります。

ということで修正した実装が以下の通りです。

use proconio::input;

fn main() {
    input! {
        n: i32,
        y: i32,
    }
    for i in 0..=n {
        for j in 0..=n {
            let k = n - i - j;
            if k >= 0 && i + j + k == n && 10000 * i + 5000 * j + 1000 * k == y {
                println!("{} {} {}", i, j, k);
                return;
            }
        }
    }
    println!("-1 -1 -1");
}

これで通るようになりました！

ただ、AIの考えたコードはもっとスマートでした。

ということでそのコードをもとに少し修正…。

use proconio::input;

fn main() {
    input! {
        n: u32,
        y: u32,
    }
    for i in 0..=n {
        for j in 0..=(n - i) {
            let k = n - i - j;
            if 10000 * i + 5000 * j + 1000 * k == y {
                println!("{} {} {}", i, j, k);
                return;
            }
        }
    }
    println!("-1 -1 -1");
}

二重目のループの最大値をn - iにすることで、必然的にkを正の整数にするようにしています。

nとyの型もu32で正常動作します。kが負の整数であるかどうかの確認作業が減ったのでいいですね。

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

実装#

実装