概要

PAST上級〜エキスパート合格を目指すアルゴリズム応用力を養う

想定読者

AtCoderで中〜上位レーティング(目安1200〜2000)を持ち、PAST上級またはエキスパート認定を取得したいエンジニアや競技プログラマー

こんな人には向いていない

• PASTの初級〜中級対策が目的の読者(初級〜中級編の前巻が先決)
• アルゴリズムをゼロから学び始める段階の人には前提知識の要求水準が高い
• Pythonを使ったことがない読者(サンプルコードはPython前提)

読了後にできるようになること

• ネットワークフロー(最大流・最小費用流)を問題の構造から識別して適用できる
• セグメント木・遅延評価セグメント木の実装と、その上で動的計画法を組み合わせる手法
• 二分探索の応用パターン(最小値の最大化・平均値最大化)を問題設定から導出できる
• 動的計画法を木・グラフ・区間など多様な部分問題構造に適用し、高速化テクニックを選択できる
• 平面走査や尺取り法・償却計算量の考え方を実際の過去問で身につける

本書のキー概念(章解説)

• 序章：アルゴリズム実技検定と本書の構成について
• 第 1 章 二分探索 発展 — 最小値の最大化・平均値最大化など、応用パターンを体系的に整理
• 第 2 章 動的計画法 発展 — 木上DP・DP高速化まで扱い、この1章だけでDPの応用力が大きく底上げされる
• 第 3 章 頻出テクニック — 変数固定・尺取り法・償却計算量をまとめて習得できる
• 第 4 章 頻出データ構造・アルゴリズム — UnionFind・LCAなど上級で頻出する構造を一通り押さえる
• 第 5 章 ネットワークフロー — 最大流・最小費用流はエキスパート水準の頻出テーマ。他の対策書では薄い領域
• 第 6 章 セグメント木 — 遅延評価まで含め、上位問題で必須の実装を丁寧に解説
• 第 7 章 セグメント木上の動的計画法(エキスパート編) — セグ木とDPの融合はエキスパート認定の壁となる難所
• 第 8 章 平面走査(エキスパート編)
• 第 9 章 難問にチャレンジ！(エキスパート編) — 過去問ベースで実力測定できる

ハイライト

• 発展的なアルゴリズムやデータ構造を解説・過去問を使った実践的なトレーニング・Pythonによるサンプルコードで、上級・エキスパート合格の点数を勝ち取ろう！(本書が中〜上級層向けの実践志向であることを最も端的に示す記述)

外部からの言及

• SE経験者の技術書読書録において、PAST上級向けの公式対策書として取り上げられ、ネットワークフローや遅延評価セグメント木を扱う点が『他の競プロ入門書にはない』領域として評価されている(qiita)

編集メモ

Qiita直接言及ほぼなし・likesデータ取得不可。ただし唯一のPAST公式上級〜エキスパート対策書として出版社・AtCoder公式が位置付けており、当該認定を目指す層には代替がない専門書

読む前に押さえておきたいこと

• AtCoderでの基本的なアルゴリズム実装経験(二分探索・基本的なDP・グラフ探索)
• Pythonの基本文法と標準ライブラリの使い方
• PAST初級〜中級レベルの問題で安定して点数を取れる水準

学習のコツ

• 第5章(ネットワークフロー)と第6章(セグメント木)は競プロの一般書でカバーされにくい領域なので、他書と並行して本書だけを参照する使い方が効率的
• 章末類題は解答前に必ず自力でアプローチを考え、詰まってから解説を読む。コードを写すだけでは得点力に結びつかない
• エキスパート編(第7〜9章)は上級編の内容が固まってから取り組む。セグ木+DPの章は特に第6章の理解が前提
• Pythonサンプルコードを他言語(C++など)で書き直す練習を加えると、本番試験での実行速度の問題に対処しやすくなる