More than 3 years have passed since last update.

AtCoderログ：0035 - ABC 087 B

Last updated at 2021-07-26Posted at 2021-07-26

問題

問題文

あなたは、$500$ 円玉を $A$ 枚、$100$ 円玉を $B$ 枚、$50$ 円玉を $C$ 枚持っています。これらの硬貨の中から何枚かを選び、合計金額をちょうど $X$ 円にする方法は何通りありますか。
同じ種類の硬貨どうしは区別できません。2 通りの硬貨の選び方は、ある種類の硬貨についてその硬貨を選ぶ枚数が異なるとき区別されます。

制約

・$0 \le A,B,C \le 50$
・$A+B+C \ge 1$
・$50 \le X \le 20,000$
・$A,B,C$ は整数である
・$X$ は $50$ の倍数である

収録されている問題セット

回答

回答1 (AC)

それぞれの硬貨の枚数 a, b, c を受け取った後、それぞれの枚数をループで回し、合計額が x 円になるかを確認していきます。コードは以下のようになりました。

abc087b-1.cpp

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a, b, c, x;
  cin >> a >> b >> c >> x;
 
  int answer = 0;
  for ( int i=0; i<=a; i++ ) {
    for ( int j=0; j<=b; j++ ) {
      for ( int k=0; k<=c; k++ ) {
        if ( 500*i+100*j+50*k==x ) {
          answer += 1;
        }
      }
    }
  }

  cout << answer << endl;
}

回答2 (AC)

回答1の無駄な処理を削りましょう。$500$ 円硬貨が i 枚、$100$ 円硬貨が j 枚のとき、残金は rest = x-500i-100j 円なので、この金額が $50$ 円硬貨で支払われるかをチェックすることで、回答1の一番内側のループをなくすことができます。rest が (1) 0 円以上、(2) 50*c 円以下、(3) 50の倍数、であるときに、rest は $50$ 円硬貨で支払うことが可能です。コードは以下のようになりました。

abc087b-2.cpp

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a, b, c, x;
  cin >> a >> b >> c >> x;
 
  int rest, answer = 0;
  for ( int i=0; i<=a; i++ ) {
     for ( int j=0; j<=b; j++ ) {
       rest = x-500*i-100*j; 
       if ( 0<=rest && rest<=c*50 && rest%50==0 ) {
         answer += 1;
       }
     }
  }

  cout << answer << endl;
}

回答1の計算回数は abc 回であったのに対し、回答2の計算回数は ab 回になっており、c 倍の高速化が実現できています。

回答3 (AC)

回答2では、使用する $500$ 円硬貨の枚数を 0 から a までループさせていましたが、x 円を支払うのに使用する硬貨の最大枚数は x/500 枚なので、ループする範囲は 0 から min(a,x/500) で良いことがわかります。同様に $100$ 円硬貨の枚数も 0 から min(b,(x-500*i)/100) でループさせれば十分です。コードは以下のようになりました。

abc087b-3.cpp

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a, b, c, x;
  cin >> a >> b >> c >> x;
 
  int rest, answer = 0;
  for ( int i=0; i<=min(a,x/500); i++ ) {
     for ( int j=0; j<=min(b,(x-500*i)/100); j++ ) {
       rest = x-500*i-100*j; 
       if ( 0<=rest && rest<=c*50 && rest%50==0 ) {
         answer += 1;
       }
     }
  }
  cout << answer << endl;
}