はじめに
自分用の備忘録
ABC087B - Coins , AtCoder Beginners Selection
※最近は音声入力と Ctrl キーを押しながら矢印キーで移動することにはまっています。その心はどちらも早い。効率化大事！
問題文
ABC087B - Coins , AtCoder Beginners Selection, https://atcoder.jp/contests/abs/tasks/abc087_b
解答例
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int A = sc.nextInt();
int B = sc.nextInt();
int C = sc.nextInt();
int X = sc.nextInt();
int count = 0;
for (int i = 0; i <= A; i++) {
for (int j = 0; j <= B; j++) {
// Point here !!!
int tempC = (X - 500 * i - 100 * j) / 50;
if (tempC >= 0 && tempC <= C) {
count ++;
}
}
}
System.out.println(count);
}
}
メモ
この問題は鉄則本のあの問題に似ているA05 - Three Cards, https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_eという問題と似ている。
この問題のポイントは、3重のforでとかいないこと。もし30のフォアでこの問題を解いてしまったときは計算量がO(N³)になってしまう。そうなるとまずたいていは計算時間に間に合わなくなる！この問題では行けますが、もう少し数が大きくなると厳しいかもです。だから、ここがポイントでした！
【3重forを2重に直す方法】
int tempC = (X - 500 * i - 100 * j) / 50;
if (tempC >= 0 && tempC <= C) {
count ++;
}
この問題のポイントとしてはSiriの数が何枚かっていうのを逆算して算出する点ですよね。 500円のコインと100円のコインとそして50円のコインを組み合わせた時にint tempCの式が成り立ちますね。でもこれだとCがマイナスになっちゃう場合もあります。なので、if文でこの条件で絞り込んでいる感じです！
【3重forの時の解法】
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int A = sc.nextInt();
int B = sc.nextInt();
int C = sc.nextInt();
int X = sc.nextInt();
int count = 0;
for (int i = 0; i <= A; i++) {
for (int j = 0; j <= B; j++) {
for (int k = 0; k <= C; k++) {
if (X == 500 * i + 100 * j + 50 * k) {
count ++;
}
}
}
}
System.out.println(count);
}
}
