Day 002-Q1 | 全探索（2重ループ）

問題

N 個の整数からなる数列 A が与えられる。数列の中から異なる 2 つの要素を選んで和を作るとき、その和が S になる組み合わせは何通りあるか。
ただし、(i, j) と (j, i) は同一の組み合わせとして数える（i < j のペアのみカウント）。

入力形式

N S
A_1 A_2 ... A_N

制約

$2 \le N \le 1000$

$0 \le S \le 2 \times 10^9$

$0 \le A_i \le 10^9$

入出力例

入力例 1

5 10
1 3 7 5 2

出力例 1

入力例 2

4 8
3 5 1 7

出力例 2

例2: 3+5=8, 1+7=8 → 2通り

ヒント (段階的開示)

ヒント1: 方向性

「異なる2要素のすべての組み合わせ」を試せばよい。N=1000 なら最大 50万通り → 十分速い。

ヒント2: アプローチ

2重ループで i < j となる全ペア (i, j) を列挙し、A[i] + A[j] == S を確認する。

ヒント3: 誘導

count = 0
for i in range(N):
    for j in range(i+1, N):
        if A[i] + A[j] == S:
            count += 1
print(count)

模範解答 (Python)

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

count = 0
for i in range(N):
    for j in range(i + 1, N):
        if A[i] + A[j] == S:
            count += 1

print(count)

Step-by-Step 解説

1入力の受け取り
N, S = map(int, input().split()) と A = list(map(int, input().split()))。

22重ループで全ペアを列挙
j = i+1 からスタートすることで「同一要素を選ばない」「重複ペアを数えない」を同時に達成。

3条件チェックとカウント
A[i] + A[j] == S なら count += 1。

計算量

時間: $O(N^2)$ — N=1000 で約50万回
空間: $O(1)$

よくあるミス

ミス	原因	正しい書き方
`j in range(N)`	同一ペアを2回カウント	`j in range(i+1, N)`
`j in range(i, N)`	i==j で同一要素	`j in range(i+1, N)`
`A[i] + A[j] = S`	代入と比較の混同	`==`

Day 002-Q1 — 全探索（2重ループ）

問題