全探索ページの位置づけ
| 項目 | 内容 |
|---|---|
| 必修度 | 必修 |
| 学習目安 | 入門〜標準 |
| 前提 | ループ・ビット集合 |
| 対象問題 | 99問（推定値あり99問、未算出0問） |
この記事のdifficulty区分は、問題を解く順番を決めるための目安です。AtCoderの公式なA〜F区分ではなく、取得できたdifficulty推定値を次の範囲に分けています。
| 学習目安 | difficulty推定値 | 問題数 |
|---|---|---|
| 入門 | difficulty < 0 | 25 |
| 標準 | 0〜799 | 40 |
| 標準〜発展 | 800〜1199 | 15 |
| 発展 | 1200以上 | 19 |
| 未算出 | — | 0 |
全探索は、候補を全部試す前に候補数を数えるアルゴリズムです。制約から間に合うと判断できれば、複雑な発想を追加せず、漏れのない列挙を選べます。
先に候補数を数える
N個から各要素を選ぶか決めるなら候補数は2^Nです。二重ループならN^2、三重ループならN^3、順列の列挙ならN!が目安になります。候補数に判定処理の計算量を掛け、制約の最大値で計算します。
| 列挙方法 | 候補数の目安 | 使える条件の例 |
|---|---|---|
| 一重ループ | N | 各候補を独立に判定する |
| 二重ループ | N^2 | Nが数千以下で判定が軽い |
| ビット全探索 | 2^N | Nが20前後で部分集合を選ぶ |
| 順列全探索 | N! | Nが8前後で順番が答えを決める |
境界のNで実際に何回判定するかを書けば、「たぶん間に合う」という曖昧さが消えます。
部分集合をビットで表す
要素iを選んだ状態を、整数のiビット目で表します。ビットが立っているかを調べると、部分集合の判定を短く書けます。
for mask in range(1 << N):
total = 0
for i in range(N):
if mask & (1 << i):
total += A[i]
if total == target:
answer += 1ビット全探索では、各ビットの意味を最初に固定します。「1が選択済み」なのか「1が未選択」なのかを途中で変えると、条件が反転します。
列挙を削る方法
候補数が制約を超える場合は、ただループを増やすのではなく、同じ答えをまとめます。
- 対称な候補を一つだけ調べる。
- 現在の値が上限を超えた時点で枝を打ち切る。
- 半分ずつ列挙して合計を二分探索する。
- 状態をメモ化し、同じ部分問題を一度だけ計算する。
ただし、枝を打ち切る条件には根拠が必要です。残りの要素を足しても条件を満たせないことが分かる場合に限り、探索を止めます。
全探索と貪欲法の境界
候補を全部試す方法は、正しさを確認しやすい反面、候補数が増えると使えません。並べ替えた順に選ぶと最適になる証明があるなら、貪欲法と不変量で選択を決めるへ切り替えます。最適な部分構造が繰り返されるなら、DPで状態と遷移を固定するへ切り替えます。
全探索を制約内に収めるでつまずきやすい境界
- ループの範囲を一つずつ確認し、同じ候補を二重に数えない。
- 空集合や0個選ぶ場合を初期状態へ含める。
- 重複する値があるとき、要素の区別が必要かを決める。
- 判定処理の中でソートしていないか確認する。
全探索を制約内に収めるで先に確認する文法・ライブラリ
まずは必須Python文法で、入力・配列・条件分岐・ループなどの基本を確認してください。問題に合わせたキュー、ヒープ、二分探索などの選び方は標準ライブラリ・定石にまとめています。
全探索を制約内に収めるの練習問題
候補数を計算してから、最も小さい列挙方法を選びます。代表問題のEditorialを読んだあと、制約を一つ変えると何が壊れるかを書き残してください。
まず解く
| 問題 | 公式解説 | 出題意図 | difficulty |
|---|---|---|---|
| ABC288 A Many A+B Problems | 公式解説 | 各テストケースのA+Bを出力する。 | -1292 |
| ABC290 A Contest Result | 公式解説 | 指定範囲の得点だけを合計する。 | -1118 |
| ABC462 A Secret Numbers | 公式解説 | Enumerate the secret numbers digit by digit and count valid ones. | -973 |
| ABC284 B Multi Test Cases | 公式解説 | Count positive entries in each test case. | -936 |
| ABC191 B Remove It | 公式解説 | Print every array value not equal to X. | -791 |
次に解く
| 問題 | 公式解説 | 出題意図 | difficulty |
|---|---|---|---|
| ABC129 A Airplane | 公式解説 | 3空港の巡回順を考え、2区間運賃の合計が最小になる順を選ぶ。 | -727 |
| ABC191 A Vanishing Pitch | 公式解説 | Check whether any power V,V^2,… up to the bound lies in the given interval. | -717 |
| ABC415 B Pick Two | 公式解説 | 公式Editorialの方針を two choice enumeration として整理する。 | -668 |
| ABC227 B KEYENCE building | 公式解説 | 正整数の組を全探索して建物の式を満たすか確認し、該当しないSの個数を数える。 | -634 |
| ABC193 B Play Snuke | 公式解説 | Among shops with stock remaining at arrival time, choose the minimum price. | -552 |
挑戦問題
| 問題 | 公式解説 | 出題意図 | difficulty |
|---|---|---|---|
| ABC433 A Happy Birthday! 4 | 公式解説 | 公式Editorialの方針を happy birthday enumeration として整理する。 | -494 |
| ABC234 B Longest Segment | 公式解説 | 全ての点対のユークリッド距離を計算し、最大値を求める。 | -464 |
| ABC335 B Tetrahedral Number | 公式解説 | Enumerate nonnegative triples in nested loops and print those whose sum is at most N in lexicographic order. | -416 |
| ABC214 B How many? | 公式解説 | 制約が小さいためa,b,cを全列挙し、和と積の2条件を満たす組を数える。 | -405 |
| ABC221 B typo | 公式解説 | 交換なしまたはSの隣接2文字を1回交換した文字列を全候補と比較する。 | -371 |
