アルゴリズム実技検定 公式テキスト［上級］〜［エキスパート］編(アルゴリズムジツギケンテイ　コウシキテキスト　ジョウキュウカラエキスパートヘン)

世界最高峰の競技プログラミングコンテストサイトの 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 問題

AtCoder が主催するアルゴリズム実技検定 (PAST) の上級〜エキスパート級を対象とした公式テキストです。著者の大槻兼資氏は『問題解決力を鍛える! アルゴリズムとデータ構造』でも知られるアルゴリズム解説の書き手で、本書では最短路問題の応用、セグメント木、フローとマッチング、動的計画法の高度なパターンなど、中〜上級者が実戦で必要とするトピックを網羅しています。

PAST の上位等級は、基本的なデータ構造を「知っている」だけでなく「問題の構造を見抜いて適用できる」力を測ります。本書はその橋渡しとして、典型的な問題パターンの分類と、各パターンに至る思考の道筋を丁寧に言語化しています。競技プログラミングで AtCoder の水色〜青程度に到達した人がさらに引き出しを増やしたい場面で効果を発揮します。

前提として基本的なアルゴリズム (ソート、 BFS/DFS 、基礎 DP) を自力で実装できることが求められます。初級〜中級の学習を終えていない段階で手に取ると歯が立たないため、先に入門書を一冊仕上げてから取り組むのが堅実です。