アルゴリズム実技検定 公式テキスト［上級］〜［エキスパート］編

世界最高峰の競技プログラミングコンテストサイトの AtCoder が主催するアルゴリズム実技検定試験「PAST」の公式対策本!

・試験問題に精通する著者陣による解説
・最強最速を目指すプログラマー・エンジニア必携

■アルゴリズム実技検定 (PAST) とは
AtCoder 株式会社が主催する検定試験で、IT 人材に求められるプログラミングスキルを可視化することを目的としています。プログラミングの基礎知識から、各種アルゴリズムの解説、数学的な問題解決方法まで、試験対策を行うことでこれからのソフトウェアエンジニアに要求される知識を見につけることができます。

■PAST の上級〜エキスパート認定まで対応
さまざまなアプローチが考えられるアルゴリズム実技検定の問題において、より適切なアルゴリズムを選択し、高速なプログラムを作成できることを目指します。

・発展的なアルゴリズムやデータ構造を解説
・過去問を使った実践的なトレーニング
・Python によるサンプルコード

複数のアルゴリズムを用いた解法を身につけ「上級」「エキスパート」合格の点数を勝ち取ろう!

CONTENTS ---

序章 アルゴリズム実技検定と本書の構成について
［上級編］
第 1 章 二分探索 発展
第 2 章 動的計画法 発展
第 3 章 頻出テクニック
第 4 章 頻出データ構造・アルゴリズム
第 5 章 ネットワークフロー
第 6 章 セグメント木
［エキスパート編］
第 7 章 セグメント木上の動的計画法
第 8 章 平面走査
第 9 章 難問にチャレンジ!
序章 アルゴリズム実技検定と本書の構成について
0.1 試験要項
0.2 本書で使用するプログラミング言語“ Python ” について
0.3 本書の構成

［上級編］
第 1 章 二分探索 発展
1.1 二分探索を適用できる問題
1.2 最小値の最大化 (最大値の最小化)
1.3 平均値最大化・中央値の最大化
1.4 まとめ

第 2 章 動的計画法 発展
2.1 動的計画法の復習 (ナップサック問題)
2.2 前回の情報を持ちながら進めていく動的計画法
2.3 さまざまな「部分問題への分け方」の動的計画法
2.4 動的計画法の高速化のためのテクニック
2.5 木上の動的計画法
2.6 その他の動的計画法

第 3 章 頻出テクニック
3.1 変数を固定して考えよう
3.2 尺取り法
3.3 償却計算量 (ならし計算量)
3.4 章末類題

第 4 章 頻出データ構造・アルゴリズム
4.1 グラフ理論の用語について
4.2 UnionFind (素集合データ構造)
4.3 最小共通祖先 (Lowest Common Ancestor)
4.4 章末類題

第 5 章 ネットワークフロー
5.1 最大流問題
5.2 最小費用流問題

第 6 章 セグメント木
6.1 セグメント木 (Segment Tree)
6.2 遅延評価セグメント木 (Lazy Segment Tree)
6.3 章末類題

［エキスパート編］
第 7 章 セグメント木上の動的計画法
7.1 問題
7.2 まとめ
7.3 章末類題

第 8 章 平面走査
8.1 問題
8.2 まとめ
8.3 章末類題

第 9 章 難問にチャレンジ!
9.1 問題

アルゴリズム実技検定 (PAST) の上級とエキスパートの認定を目標にする人のための、主催者側が関わる対策書です。『アルゴリズム実技検定 公式テキスト［上級］〜［エキスパート］編』は大槻兼資、杉江祐哉、中村謙弘の 3 名が著し、AtCoder 株式会社と高橋 直大が監修して、マイナビ出版から 2023 年 3 月に発売されました。版元は本書を PAST の「公式対策本」と案内し、発展的なアルゴリズムやデータ構造の解説、過去問を使った実践的なトレーニング、Python によるサンプルコードの 3 点を柱に挙げています。刊行時の略歴によれば、高橋 直大は AtCoder の代表取締役社長、大槻兼資は『問題解決力を鍛える! アルゴリズムとデータ構造』 (講談社) の著者で、杉江祐哉と中村謙弘はそれぞれ tsutaj、kenkoooo というユーザー名で AtCoder などのコンテストに参加してきた書き手です。

序章と 9 章、上級編からエキスパート編への並び

序章「アルゴリズム実技検定と本書の構成について」で試験要項と、本書が使う言語 Python について説明したうえで、本文は 2 部に分かれます。上級編は第 1 章「二分探索 発展」、第 2 章「動的計画法 発展」、第 3 章「頻出テクニック」、第 4 章「頻出データ構造・アルゴリズム」、第 5 章「ネットワークフロー」、第 6 章「セグメント木」の 6 章です。第 1 章は最小値の最大化や平均値と中央値の最大化、第 2 章はナップサック問題の復習から木上の動的計画法と高速化のためのテクニック、第 3 章は尺取り法と償却計算量、第 4 章は UnionFind と最小共通祖先、第 5 章は最大流問題と最小費用流問題、第 6 章は遅延評価セグメント木までを扱います。エキスパート編は第 7 章「セグメント木上の動的計画法」、第 8 章「平面走査」、第 9 章「難問にチャレンジ!」の 3 章で、第 7 章と第 8 章は問題、まとめ、章末類題の 3 節で構成されます。第 3 章、第 4 章、第 6 章、第 7 章、第 8 章の末尾には章末類題が置かれています。

上位の等級で効いてくる、計算量を一段落とす発想

競技プログラミング の問題は、素直に書けば答えは出るものの、制限時間に収まらないという形で難しくなります。上位の等級で求められるのは、全探索で書ける解法を、問題の構造を使って 計算量 の小さい解法へ置き換える力です。たとえば答えの値を決め打ちして条件を満たすかを判定し、その判定を二分探索で回すと、最適化の問題が判定の問題に変わります。区間の和や最小値を何度も問い合わせる問題では、配列を毎回走査する代わりにセグメント木で 1 回あたりの処理を対数時間に抑えられ、遅延評価を加えると区間への一括更新にも対応できます。動的計画法 も、状態の持ち方や遷移の高速化を工夫できるかどうかで扱える入力の大きさが大きく変わります。本書の章立ても、二分探索と動的計画法を「発展」として取り上げ直し、エキスパート編でセグメント木と動的計画法を組み合わせる章へ進む並びです。

Python で書かれたコードと、検定の受け方

サンプルコードは Python で書かれています。検定の公式ページによれば、PAST は選択式ではなく実際にプログラムを書いて実行し、その結果で能力を判定する実践型の検定で、AtCoder で利用できるすべてのプログラミング言語が使えます。そのため C++ や Rust で受験する人は、本書のコードを自分の言語へ読み替えながら進めることになります。実施の方式は 2026 年 10 月時点の公式ページで、6 月と 12 月の第一土曜日 13:00 から 5 時間のリアルタイム受験と、その後に次の検定日の前日まで受けられる通常受験の 2 本立てと案内されており、2026 年 12 月 5 日から第 26 回が予定されています。序章の試験要項は刊行時のものなので、受験の前には公式ページで条件を確かめてください。

中級を越えた先で手が止まっている人に

書名のとおり上級からエキスパートの等級を対象にした本で、第 2 章はナップサック問題の復習から、第 4 章はグラフ理論の用語の整理から入るものの、扱う題材の中心はネットワークフローやセグメント木、平面走査です。プログラミングそのものやアルゴリズムの基礎をこれから学ぶ段階であれば、先に入門向けの教材で土台を作るほうが近道になります。中級までの問題は解けるのに、上位の等級の問題になると方針が立たない人、あるいは過去問の解説を読んでも使われている手法の名前で止まってしまう人には、版元が「試験問題に精通する著者陣による解説」と紹介する本書が、手法ごとに整理された章立てで次の等級へ届くための手がかりになります。