全探索は「漏れなく、重複なく」
まず小さな制約で動く正解を作る。全探索はその基準になります。候補を列挙し、条件を確かめ、答えを更新します。
言語：Python / 計算量：O(N²)
前提：制約から計算量を見積もる
考え方
- 何を1候補とするか決めます。
- 組を選ぶなら i < j にして同じ組を2度数えません。
- 候補数と判定の計算量を掛けます。
具体例
[1,2,3] から和が4になる異なる2要素を選ぶと (1,3) の1組です。
実装
a = [1, 2, 3]
ans = 0
for i in range(len(a)):
for j in range(i + 1, len(a)):
if a[i] + a[j] == 4:
ans += 1
print(ans)注意する条件
i=j を許すか、順序を区別するかを先に確かめます。
確認問題
[1,2,3,4] で和5のペア i<j は何組？
解答と理由
2
(1,4) と (2,3) の2組です。
実装課題
N K と配列 A が2行。i<j かつ A_i+A_j=K の組数。1 ≤ N ≤ 100、0 ≤ A_i,K ≤ 200。
入力:
4 5
1 2 3 4
出力:
2参考実装
n, k = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
for i in range(n):
for j in range(i + 1, n):
ans += a[i] + a[j] == k
print(ans)実戦につなげる補講
一度に全て読まなくて大丈夫です。今日は1節と1問から。
候補を列挙してから、判定を書く
候補の種類を1文にします。「異なる2つの添字」ならi<j。「各要素を選ぶ・選ばない」なら2^N通り。何を全探索するかが曖昧なままforを書き始めないようにします。
列挙の回数×1候補の判定コストが基本です。候補がN²通りでも、判定がsumでO(N)なら全体はO(N³)になります。
全探索は捨てずに、正しさの物差しにする
最初から速い式を思いつく必要はありません。小さい制約で動く愚直解を先に書くと、高速版と結果を比べられます。速いが間違った解法より、遅いが正しい解法の方が改善の出発点になります。
1変数を決めると、残りは計算で分かる？
合計がTになる2数を探すなら、xを決めたとき必要な相手はT−xです。全てのyを調べる代わりに、その値を調べる仕組みを作れます。ただし同じ要素を2回使うことや重複の数え方には注意します。
段階式の追加演習
1. 列挙の漏れを確認
添字0,1,2,3から異なる2個を選ぶ全組合せを列挙して。
ヒント
小さい方の添字を先に書く。
解答と理由
(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)の6通り。
2. 判定コストを掛ける
全てのl,rについてsum(a[l:r])を計算する。なぜO(N²)ではない？
ヒント
列挙が二乗でも、1回のsumの長さは一定ではない。
解答と理由
区間が約N²個あり、長い区間の合計計算にN程度かかる。全区間長の総和はN(N+1)(N+2)/6なのでO(N³)。
3. 実装：一致する組
数列aの異なる2添字i<jで、a[i]+a[j]=targetとなる組数を返すcount_pairsを書いて。a=[2,2,5,8],target=10なら2。
ヒント
値が同じでも添字が違えば別要素。jはi+1から。
解答と理由
まずO(N²)の基準実装を作る。重複のある入力でも添字の組ごとに数えられる。
def count_pairs(a, target):
answer = 0
for i in range(len(a)):
for j in range(i + 1, len(a)):
if a[i] + a[j] == target:
answer += 1
return answer4. 高速化の言語化
前の問題を大きいNに対応させたい。保存すると役立つ情報は？
ヒント
現在のxに必要な相手はtarget−x。過去に何個あったか。
解答と理由
過去の値の出現回数を辞書で保存する。現在の値を辞書へ追加する前に相手の個数を足すと、同じ添字の再利用と二重カウントを防げる。辞書の講義で実装する。
公式過去問への橋渡し
ABC143 D / 公式解説PDF
3要素の全探索から、2要素を固定して残りの候補数を境界で求める発想へ進む。
公式問題 / 公式解説見本を閉じて確認
- 何を繰り返しているかを説明できる
- 使える条件と使えない条件を1つずつ言える
- 見本を閉じて実装し、小さい入力で確かめられる