/ 
実行時間制限: 2 sec / メモリ制限: 256 MB
問題文
ある果物屋では、リンゴ・パイナップルがそれぞれN個売られています。i個目のリンゴ、パイナップルはそれぞれA_i円、P_i円です。
リンゴ・パイナップルをそれぞれ1つずつ選んで購入しようとするとき、合計金額が丁度S円になるような買い方が何通りあるか求めてください。
ただし、同じ値段の同じ種類の商品でも区別します。たとえば同じ値段のリンゴが複数あった場合、それらを買う場合は別の買い方として数えます。パイナップルについても同様です。また、リンゴ・パイナップルを買う順番は考慮しないものとします。
#include <bits/stdc++.h>
using namespace std;
int main() {
int N, S;
cin >> N >> S;
vector<int> A(N), P(N);
for (int i = 0; i < N; i++) {
cin >> A.at(i);
}
for (int i = 0; i < N; i++) {
cin >> P.at(i);
}
// リンゴ・パイナップルをそれぞれ1つずつ購入するとき合計S円になるような買い方が何通りあるか
// ここにプログラムを追記
}
制約
- 0≦N≦100
- 0≦S≦1000
- 1≦A_i, P_i≦500 (1 ≦ i ≦ N)
- A_i, P_i (1 ≦ i ≦ N)は整数
入力
入力は次の形式で標準入力から与えられます。
N S A_1 A_2 \cdots A_N P_1 P_2 \cdots P_N
出力
リンゴ・パイナップルをそれぞれ1つずつ購入しようとするとき、合計金額が丁度S円になるような 買い方が何通りあるかを出力してください。
出力の最後には改行が必要です。
ジャッジでは以下の入力例以外のケースに関してもテストされることに注意。
入力例1
3 400 100 100 130 270 300 250
出力例1
3
合計が400円になる買い方は以下の3通りです。
1つ目のリンゴ、2つ目のパイナップルを購入すると、100円 + 300円 = 400円となります。
2つ目のリンゴ、2つ目のパイナップルを購入すると、100円 + 300円 = 400円となります。
3つ目のリンゴ、1つ目のパイナップルを購入すると、130円 + 270円 = 400円となります。
1つ目のリンゴと2つ目のリンゴがどちらも100円ですが、別の買い方として数えることに注意してください。
入力例2
10 600 70 110 90 120 90 20 260 150 220 150 170 100 250 350 60 280 450 460 20 220
出力例2
2
入力例3
3 200 100 100 100 100 100 100
出力例3
9
入力例4
1 0 100 200
出力例4
0
合計0円で買うことはできません。
ヒント
- ループを使わないで書く
- パターンを見つける
- ループで書き直す
に沿って書く場合の流れをヒントで説明します。
まずは自分で考えてみて、詰まったら見てみましょう。
ヒント1 (ループを使わないで書く)
クリックでヒントを見る
合計がS円になるような買い方が何通りあるかを求めるので、 すべての組み合わせをif文で確認できれば答えが求まるはずです。
一般のNでは考えにくいので、試してみるときはNを小さい値で仮定してみるとよいです。 N = 3のケースを全て書き出してみます。(添え字として0始まりの値を使っている点に注意してください。)
int ans = 0;
if (A.at(0) + P.at(0) == S) {
ans++;
}
if (A.at(0) + P.at(1) == S) {
ans++;
}
if (A.at(0) + P.at(2) == S) {
ans++;
}
if (A.at(1) + P.at(0) == S) {
ans++;
}
if (A.at(1) + P.at(1) == S) {
ans++;
}
if (A.at(1) + P.at(2) == S) {
ans++;
}
if (A.at(2) + P.at(0) == S) {
ans++;
}
if (A.at(2) + P.at(1) == S) {
ans++;
}
if (A.at(2) + P.at(2) == S) {
ans++;
}
添え字の変化に着目するとパターン化できそうです。
ヒント2 (パターンを見つける)
クリックでヒントを見る
変数i, jを導入してi番目のリンゴ、j番目のパイナップルを買う場合を考えます。
条件式は次のようになります。
if (A.at(i) + P.at(j) == S) {
ans++;
}
あとはi, jを網羅的に動かして上の文を実行できればよいです。
ヒント3 (ループで書き直す)
クリックでヒントを見る
変数i, jを導入してi番目のリンゴ、j番目のパイナップルを買う場合の判定文は次のようになります。
if (A.at(i) + P.at(j) == S) {
ans++;
}
i, jはそれぞれ別々に0からN - 1までの値を取ります。
このように変数(ここではi, j)の組み合わせを列挙したい場合は、多重ループを用います。
今回の場合は変数がi, jの2つなので、次のような二重ループになります。
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
// i, jを使う
}
}
テスト入出力
書いたプログラムがACにならず、原因がどうしてもわからないときだけ見てください。
クリックでテスト入出力を見る
テスト入力1
10 520 430 310 230 390 130 220 70 370 400 160 390 120 450 30 250 140 200 300 270 30
テスト出力1
4
テスト入力2
100 500 247 365 116 339 302 274 383 230 444 136 12 100 92 498 16 190 252 438 404 493 46 105 197 254 180 455 233 280 289 286 301 205 200 477 273 481 494 287 202 211 327 359 341 4 51 336 101 416 142 35 401 457 61 179 33 362 180 176 60 247 500 44 279 372 424 439 224 99 379 322 110 159 383 143 164 435 6 461 61 391 38 225 163 273 222 156 33 300 42 228 164 22 244 66 28 208 243 36 417 93 62 231 388 7 434 37 474 357 262 182 36 298 426 331 252 129 113 156 111 441 375 210 492 499 302 287 493 170 262 233 475 406 72 401 468 156 220 0 410 12 223 150 240 159 345 239 455 404 419 19 46 174 499 218 423 145 196 307 401 260 470 424 171 284 437 44 500 316 156 192 422 391 365 485 145 22 410 124 110 182 28 143 203 289 95 85 415 401 191 268 262 341 391 130 364 274 379 443 53 389
テスト出力2
15
テスト入力3
100 1000 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500
テスト出力3
10000
解答例
必ず自分で問題に挑戦してみてから見てください。
クリックで解答例を見る
解答例1
#include <bits/stdc++.h>
using namespace std;
int main() {
int N, S;
cin >> N >> S;
vector<int> A(N), P(N);
for (int i = 0; i < N; i++) {
cin >> A.at(i);
}
for (int i = 0; i < N; i++) {
cin >> P.at(i);
}
// リンゴ・パイナップルをそれぞれ1つずつ購入するとき合計S円になるような買い方が何通りあるか
int ans = 0; // 買い方が何通りあるか
// 実際に全ての買い方を試してみて、合計がS円ならカウントアップ
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (A.at(i) + P.at(j) == S) {
ans++;
}
}
}
cout << ans << endl;
}
解答例2 (範囲for文を用いた解法)
#include <bits/stdc++.h>
using namespace std;
int main() {
int N, S;
cin >> N >> S;
vector<int> A(N), P(N);
for (int i = 0; i < N; i++) {
cin >> A.at(i);
}
for (int i = 0; i < N; i++) {
cin >> P.at(i);
}
// リンゴ・パイナップルをそれぞれ1つずつ購入するとき合計S円になるような買い方が何通りあるか
int ans = 0; // 買い方が何通りあるか
// 実際に全ての買い方を試してみて、合計がS円ならカウントアップ
for (int x : A) {
for (int y : P) {
if (x + y == S) {
ans++;
}
}
}
cout << ans << endl;
}