競技プログラミング

ABC085C – Otoshidama

https://atcoder.jp/contests/abs/tasks/abc085_c

この問題は3種類の紙幣を使って特定の合計金額を作ることができるか、そしてそれが可能な場合はどのような組み合わせで作ることができるかを求める問題です。しかし、全ての可能な組み合わせを試すと非常に時間がかかるため、より効率的な方法を考えなければなりません。

まず、紙幣の額面は1000円、5000円、10000円の3種類です。これらの額面を見て、1000円が最小単位であることがわかります。したがって、まずは1000円札の枚数を最大限にし、それから5000円札と10000円札で補っていくという方法が考えられます。

例えば、青橋くんが言うには、彼が祖父から受け取ったお年玉袋にはお札が9枚入っていて、合計で45000円だったとしましょう。まずは全て1000円札であると仮定して、必要な枚数を求めます。45000円 / 1000円 = 45枚ですが、これはお札の枚数9枚よりも多いです。したがって、この場合は全て1000円札であるとは限らないことがわかります。

次に、5000円札を1枚追加し、それによって減らせる1000円札の枚数を求めます。5000円 / 1000円 = 5枚なので、5000円札を1枚追加すると1000円札を5枚減らすことができます。これを繰り返し、お札の枚数が9枚になるまで5000円札と10000円札を追加します。

そして、その結果が目標の合計金額と一致するか確認します。一致すればその組み合わせが答えとなります。しかし、一致しない場合はそのような組み合わせは存在しないということになります。

ここで紹介した方法は貪欲法と呼ばれるアルゴリズムです。最初に1000円札を最大限にするという「貪欲」な選択をし、それから最適な解を見つけるために少しずつ修正していくという方法です。

また、この問題は全探索でも解くことが可能です。全ての組み合わせを試す方法ですが、お札の最大枚数が2000枚であり、それぞれのお札を0枚から最大枚数まで試すとなると、計算量が多くなりすぎます。しかし、額面が大きいお札から順に、そのお札で出来るだけ合計金額を満たすように選んでいき、最後に1000円札で残りを満たすという方法をとると、全探索でも十分な速度で解を得ることができます。

ここでは具体的なSwiftのコードを示します。それぞれの額面の紙幣について、最大から0までの枚数を試してみます。必要な合計金額からそれぞれの紙幣の額面と枚数を引いていき、最終的に全ての紙幣でちょうど合計金額を作れたときの紙幣の枚数を出力します。それが見つからなかった場合は”-1 -1 -1″を出力します。

import Foundation
let line = readLine()!.split(separator: " ").map { Int($0)! }
let (N, Y) = (line[0], line[1])

for x in 0...N {
    for y in 0...(N - x) {
        let z = N - x - y
        if 10000 * x + 5000 * y + 1000 * z == Y {
            print("\(x) \(y) \(z)")
            exit(0)
        }
    }
}

print("-1 -1 -1")

このプログラムは、まず標準入力から値を読み取り、整数に変換してNYに格納します。それぞれの額面の紙幣について、最大から0までの枚数を試してみます。xyのループが終わった時点で、zN - x - yと計算することができます。すなわち、合計の枚数Nから10000円札と5000円札の枚数を引いたものが1000円札の枚数になります。

次に、それぞれの額面と枚数をかけて合計し、それがYと一致するかを確認します。もし一致するなら、その組み合わせを出力してプログラムを終了します。

どの組み合わせも合計金額Yと一致しなかった場合は、"-1 -1 -1"を出力します。これは、そのような組み合わせは存在しないことを意味します。

このコードは効率的な解法であり、問題の制約内であれば十分に高速に動作します。このように考えて解答を導く能力は、競技プログラミングだけでなく、実際のプログラミングの現場でも非常に重要です。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です