AtCorderのABC087B - Coins問題を全探索で解く

AtCorderの問題ABC087B-Coinsを全探索で解く解法を書きます。
問題は以下になります。

問題

あなたは、500 円玉を A 枚、100 円玉を B 枚、50 円玉を C 枚持っています。
これらの硬貨の中から何枚かを選び、合計金額をちょうど X円にする方法は何通りありますか。

同じ種類の硬貨どうしは区別できません。2 通りの硬貨の選び方は、ある種類の硬貨についてその硬貨を選ぶ枚数が異なるとき区別されます。

制約

0≤A,B,C≤50
A+B+C≥1
50≤X≤20,000
A,B,Cは整数である
Xは 50 の倍数である

入力

入力は以下の形式で標準入力から与えられる。

A
B
C
X

出力

硬貨を選ぶ方法の個数を出力せよ。

問題解説

同じ硬貨の枚数が重複しない、組み合わせの総数を求めています。
制限を見る限り一つの硬貨につき50枚までとリミットが少ないので、
全探索で解いてみることにしました。

解法のコツ

数値の一番大きな硬貨500円を選択するかしないかの組み合わせから試すことで、
合計金額がマイナスになった時に、後半の組み合わせを無視することができるので、
大 ⇨ 小という風にコインの組み合わせをループを組んでいきます。

500円を選択するかしないかの組み合わせをチェックする場合は、
forで500円の個数枚分ループを回すとして、
最初の0は500円を未選択の状態とし、1の場合を1枚選択した状態、
2の場合を2枚選択した状態とし、目標の合計金額から枚数分減らしていきます。

合計金額から500円を引いた時に、合計金額がマイナスとなった時は、それ以降計算しても合計金額が0になることはないので、
組み合わせのループを抜けて、組み合わせの数を表示させるようにしました。

c++での解法例

#include <iostream>

using namespace std;

int main(){
    int a,b,c,sum;
    int success = 0;
    cin >> a;
    cin >> b;
    cin >> c;
    cin >> sum;
    
    // 500
    for(int i = 0;i <= a;++i){
        // 初回は選ばない
        if(i != 0){
            // 2回目以降は選択するつまり、合計金額を減らす
            sum -= 500;
            if(sum == 0){
                success++;
                i = a;
            }
            // -になった場合これ以降の組み合わせは無駄になる
            if(sum < 0){
                break;
            }
        }
        // 100
        for(int j = 0;j <= b;++j){
            // 初回は選ばない
            if(j != 0){
                sum -= 100;
                if(sum == 0){
                    success++;
                    sum += j * 100;
                    j = b;
                    break;
                }
                // 金額がマイナスになったら、合計金元に戻して500円の組み合わせから
                else if(sum < 0){
                    sum += j * 100;
                    break;
                }
            }
            // 50
            for(int k = 0;k < c;++k){
                sum -= 50;
                if(sum == 0){
                    success++;
                    sum += (k + 1) * 50;
                    k = c;
                    break;
                }
                else if(sum < 0){
                    break;
                }
                // ループが終了したら金額を戻す
                if(k + 1 >= c){
                    sum += (k + 1) * 50;
                }
            }
            // ループが終了したら金額を戻す
            if(j + 1 > b){
                sum += j * 100;
            }
        }
    }
    
    cout << success << endl;
    return 0;
}