木・グラフページの位置づけ
| 項目 | 内容 |
|---|---|
| 必修度 | 重要 |
| 学習目安 | 標準 |
| 前提 | 隣接リスト・訪問管理 |
| 対象問題 | 3問（推定値あり3問、未算出0問） |
この記事のdifficulty区分は、問題を解く順番を決めるための目安です。AtCoderの公式なA〜F区分ではなく、取得できたdifficulty推定値を次の範囲に分けています。
| 学習目安 | difficulty推定値 | 問題数 |
|---|---|---|
| 入門 | difficulty < 0 | 1 |
| 標準 | 0〜799 | 0 |
| 標準〜発展 | 800〜1199 | 0 |
| 発展 | 1200以上 | 2 |
| 未算出 | — | 0 |
一般的な探索・最短路・Union-Find・木DPに当てはめにくい、グラフの構成や特殊な性質をまとめます。まず専用ページへ移せないかを確認し、残った問題だけを扱います。
問題ごとの細かな実装は異なりますが、最初に確認する条件は共通しています。
木・グラフの見分け方
- 頂点と辺の構造そのものを出力・検証する
- 一般的な探索より構造上の不変条件が答えを決める
- 専用ページの実装パターンをそのまま再利用できない
木・グラフの実装前チェック
- 探索・最短路・Union-Find・木のどれで書けるか先に確認する
- グラフの次数や連結性などの不変条件を書く
- 構成したグラフを小さい入力で検証する
先に確認する文法・ライブラリ
まずは必須Python文法で、入力・配列・条件分岐・ループなどの基本を確認してください。問題に合わせたキュー、ヒープ、二分探索などの選び方は標準ライブラリ・定石にまとめています。
代表問題で実装を確認する
最初の一問として、ABC285 A Edge Checker 2（公式解説）を解きます。完全二分木では、頂点Bの親はBを2で割った整数です。親がAと一致するかだけを確認します。
A, B = map(int, input().split())
print('Yes' if B // 2 == A else 'No')割り算1回のO(1)時間・O(1)メモリです。木全体を作る必要はありません。
木・グラフの学ぶ順番
このページでは全件を一度に並べず、difficultyの推定値を目安に代表問題を段階分けしています。難易度が未算出の問題は、制約と出題意図を先に確認します。
まず解く
| 問題 | 公式解説 | 出題意図 | difficulty |
|---|---|---|---|
| ABC285 A Edge Checker 2 | 公式解説 | Check whether A is the parent of B in the implicit binary heap tree. | -1022 |
| ABC321 E H. Complete Binary Tree | 公式解説 | Count nodes at depth d in a bounded binary tree using subtree sizes. | 1627 |
| ABC140 F Many Slimes | 公式解説 | 完全二分木の葉へ大きい値から割り当て、黒く塗った頂点で分割される連結成分の容量を保ちながら同値の配置可否を判定する。 | 2105 |
問題文を読んだら、まず「見分け方」のどれに当たるかを一行で記録します。当てはまらない問題は、別のページへ移す判断自体を復習材料にします。
