EX15 - 果物屋さんでお買い物 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

説明ページに戻る

問題文

ある果物屋では、リンゴ・パイナップルがそれぞれN個売られています。i個目のリンゴ、パイナップルはそれぞれA_i円、P_i円です。

リンゴ・パイナップルをそれぞれ1つずつ選んで購入しようとするとき、合計金額が丁度S円になるような買い方が何通りあるか求めてください。

ただし、同じ値段の同じ種類の商品でも区別します。たとえば同じ値段のリンゴが複数あった場合、それらを買う場合は別の買い方として数えます。パイナップルについても同様です。また、リンゴ・パイナップルを買う順番は考慮しないものとします。

制約

  • 0\le N\le 100
  • 0\le S\le 1000
  • 1\le A_i, P_i\le 500\ (1 \le i \le N)
  • 入力される値はすべて整数である

入力

入力は次の形式で標準入力から与えられます。

N S
A_1 A_2 \cdots A_N
P_1 P_2 \cdots P_N

出力

リンゴ・パイナップルをそれぞれ1つずつ購入しようとするとき、合計金額が丁度S円になるような買い方が何通りあるかを出力してください。

サンプルプログラム

入力を受け取るサンプルプログラムを以下に示します。

N, S = map(int, input().split())

A = list(map(int, input().split()))
B = list(map(int, input().split()))

# リンゴ・パイナップルをそれぞれ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. ループを使わないで書く
  2. パターンを見つける
  3. ループで書き直す

に沿って書く場合の流れをヒントで説明します。

まずは自分で考えてみて、詰まったら見てみましょう。

ヒント1 (ループを使わないで書く)

クリックでヒントを見る

合計がS円になるような買い方が何通りあるかを求めるので、
すべての組み合わせをif文で確認できれば答えが求まるはずです。

一般のNでは考えにくいので、試してみるときはNを小さい値で仮定してみるとよいです。
N = 3のケースを全て書き出してみます。(添え字として0始まりの値を使っている点に注意してください。)

ans = 0

if A[0] + P[0] == S:
    ans += 1
if A[0] + P[1] == S:
    ans += 1
if A[0] + P[2] == S:
    ans += 1

if A[1] + P[0] == S:
    ans += 1
if A[1] + P[1] == S:
    ans += 1
if A[1] + P[2] == S:
    ans += 1

if A[2] + P[0] == S:
    ans += 1
if A[2] + P[1] == S:
    ans += 1
if A[2] + P[2] == S:
    ans += 1

添え字の変化に着目するとパターン化できそうです。

ヒント2 (パターンを見つける)

クリックでヒントを見る

変数i, jを導入してi番目のリンゴ、j番目のパイナップルを買う場合を考えます。
条件式は次のようになります。

if A[i] + P[j] == S:
    ans += 1

あとはi, jを網羅的に動かして上の文を実行できればよいです。

ヒント3 (ループで書き直す)

クリックでヒントを見る

変数i, jを導入してi番目のリンゴ、j番目のパイナップルを買う場合の判定文は次のようになります。

if A[i] + P[j] == S:
    ans += 1

i, jはそれぞれ別々に0からN - 1までの値を取ります。
このように変数(ここではi, j)の組み合わせを列挙したい場合は、多重ループを用います。
今回の場合は変数がi, jの2つなので、次のような二重ループになります。

for i in range(N):
    for j in range(N):
        # 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 499 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 1 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

# 入力値を読み込む
N, S = map(int, input().split())
A = list(map(int, input().split()))
P = list(map(int, input().split()))

# りんごとパイナップルを1つずつ購入する組み合わせが、合計S円になる方法の数を計算する
ans = 0  # 方法の数をカウントするための変数

# すべての組み合わせをチェック
for i in range(N):
    for j in range(N):
        if A[i] + P[j] == S:
            ans += 1

# 結果を出力
print(ans)

解答例2 (Listに対するfor文を用いた解法)

# 入力値を読み込む
N, S = map(int, input().split())
A = list(map(int, input().split()))
P = list(map(int, input().split()))

# りんごとパイナップルを1つずつ購入する組み合わせが、合計S円になる方法の数を計算する
ans = 0  # 方法の数をカウントするための変数

# すべての組み合わせをチェック
for x in A:
    for y in P:
        if x + y == S:
            ans += 1

# 結果を出力
print(ans)