(書評)「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造(通称:TLE本/AOJ本/螺旋本)」〜オンラインジャッジを使って効率的にアルゴリズムとデータ構造を学べる
競プロにハマってアルゴリズムとデータ構造を体系的に学びたくなったら
おすすめできる人
おすすめできない人
本の内容
会津大学(競技プログラミングのサイト，Aizu Online Judgeを運営している大学)の渡部教授が著した，その名の通りデータ構造とアルゴリズムに関する本です．
秋葉拓哉さんという有名な競技プログラミング界の重鎮が協力しているということもあり，内容に関して信頼できます．
読んだ感想
簡潔性 > 厳密性
洋書のように分厚い本に過剰と言われるまでの説明がされているというよりは，分厚くならならずに(十分厚いですが)網羅的にアルゴリズムを扱うため，できるだけ簡潔に書いた本という印象です．
厳密に，そして数理的に理解した人はこの本の後に洋書も読んでみてはいかがでしょうか．
実装が容易
AOJのコースに問題があり，書いたコードをそのまま試せるので実装しながら理解を確かめます．
題名に「プログラミングコンテストのための」と入っていますが，実装しながらアルゴリズムが理解できるのでプログラミングコンテストに興味がない人にも勧められる本です．
ただ，個人的にはC言語だけでしか実装されていないものも多く，競技プログラミングで最も使われているC++ですべて実装しなかったのはなぜかという疑問はあります(文法は似ていますが...)．
ちなみに私はコードを写経して提出していました(あくまで理解してで，ただ写経するだけだと意味はないかもしれないです)．
全部実装すると時間がかかりすぎる&理解できれば後は実践あるのみだと思ったからなんですがこれでいいのかな？
上級者の方は教えてください．
わかりやすいが
わかりやすく書いているとは思いますが，正直初心者がこれをそのまま読んで理解できるかは微妙です．
少なくともポインタや構造体，クラスを扱って何かしらのプログラムを組んだことが無いと難しいのではないかと思います．
改善案として
- 変数名をよりわかりやすくする
- コメントの量を増やす
ことが挙げられると思います．
本書が難しいという方はまず本書の姉妹書でプログラミングコンテストに入門しながらCやC++の文法を学べる本もあるのでそちらを読んでみてはいかがでしょうか？
この本の目次
この本を買おうか迷っている人のためにもう少し詳しめに説明したものを書きます．
1章はPart1として「準備編」 2章から13章はPart2として「基礎編」 14章から19章はPart3として「応用編」 となっています．
また，付録として本書で扱った内容で解くことが出来る，AOJの問題が紹介されています．
Part1 準備編
競技プログラミングでの心得みたいなのが書いてあります．
興味のない人は飛ばしても大丈夫です．
Part2 基礎編
よく競技プログラミングをやっている人達が話している典型的なアルゴリズムの宝庫という気がしました．
基礎というのは簡単という意味ではなくすべての土台ということでしょう．
応用編以降でも出てきますし，そもそも基礎編の内容が他の基礎編に絡んでいるのでここはかなりしっかりやったほうが良さそうです．
3章 初頭的整列
データの並びをいかにして整えるか，その基本的な方法，ソートについて学びます．
ここでは挿入ソート(Insertion Sort)，バブルソート(Bubble Sort)，選択ソート(Selection Sort)，シェルソート(Shell Sort)について扱っています．
プログラミング経験がある方ならわざわざするまでも無いかもしれません(？)
4章 データ構造
データを効率的に扱えるような形式について学びます．
ここではスタック(Stack)，キュー(Queue)，双方向連結リスト(Doubly linked list)，標準テンプレートライブラリ(Standard Template Library)について扱います．
STLはstack, queue, vector, listの使い方を紹介しています．
勉強した時点では多くのことが学べましたが，今では当たり前になってしまいました．
5章 探索
データの集合から目的の要素を探し出す方法を学びます．
ここでは線形探索(Linear Search)，二分探索(Binary Search)，ハッシュ(Dictionary)，標準ライブラリによる探索，探索の応用について扱っています．
標準ライブラリによる検索では，イテレータ，lower_boundの使い方を紹介しています．
ここも本当に基礎ですね．
6章 再帰・分割統治法
与えられた問題を分解した小さな問題を解くことで，元の問題をより簡単に解く方法をを学びます．
ここでは全探索(Exhaustive Search)，コッホ曲線(Koch Curve)について扱っています．
コッホ曲線では回転行列の知識を使うので，行列の勉強をしておいた方がいいかもしれません(忘れてしまった人は検索しましょう)．
7章 高等的整列
前章の内容(再帰・分割統治法)を用いて，より高速なソートを学びます．
ここではマージソート(Merge Sort)，パーティション(Partition)，クイックソート(Quick Sort)，計数ソート(Counting Sort)，標準ライブラリによる整列，反転数(The Number of Inversions)，最小コストソート(Minimum Cost Sort)について扱っています．
標準ライブラリによる整列ではvectorでのsortと，配列でのsortを紹介しています．
前の章の話題が入るようになり難しくなり始めます．
8章 木
木構造という階層的な構造を表すのに適したデータ構造を学びます．
ここでは根付き木(Rooted Trees)，二分木(Binary Tree)，木の巡回(Tree Walk)，木の復元(Reconstruction of the Tree)について扱っています．
木は概念も難しいですし，実装が...しかしこれ以降に学ぶ内容で頻出するので是が非でも抑えたいです．
9章 二分探索木
木構造を使ってデータの効率的な追加・削除・探索を学びます．
ここではに挿入，探索，削除，標準ライブラリによる集合の管理ついて扱っています．
標準ライブラリによる集合の管理ではset，mapを紹介しています．
二分探索木も木と同じですね．概念も実装も難しいですが理解しないとまずいです．
10章 ヒープ
木構造を応用してデータの持つキーを基準としてデータを取り出すデータ構造，ヒープを学びます．
ここでは完全二分木(Complete Binary Tree)，最大・最小ヒープ(Maximum Heap)・優先度付きキュー(Priority Queue)，標準ライブラリによる優先度付きキューについて扱っています．
標準ライブラリによる優先度付きキューではpriority_queueを紹介しています．
競プロでこれを実践で使っている人は強い方が多いという印象です(使えない)．
11章 動的計画法
計算結果をメモリに記憶して，同じ計算を繰り返す無駄を省く動的計画法を学びます．
ここではフィボナッチ数列(Fibonacci Number)，最長共通部分列(Longest Common Subsequence)，連鎖行列積(Matrix Chain Multiplication)について扱っています．
基礎編なので簡単な動的計画法しか出てきませんが，応用編もそんなに難しいのはでません．
12章 グラフ
コンピュータで扱う多くの問題の「対象」とそれらの「関係」を抽象的に表現したグラフを学びます．
ここではグラフの表現(Graph)，深さ優先探索(Depth First Search)，幅優先探索(Breadth First Search)，連結成分(Connected Components)について扱っています．
出ましたグラフ．SNSを使う人はなんとなくイメージしやすいかもしれません．
13章 重み付きグラフ
前回のグラフに重み(値)が設定された重み付きグラフを学びます．
ここでは最小全域木(Minimum Spanning Tree)，単一始点最短経路(Single Source Shortest Path)について扱っています．
最小全域木ではプリムのアルゴリズム，単一始点最短経路ではダイクストラのアルゴリズムと，それを優先度付きキューで実装したものを紹介しています．
グラフ同様抽象的な木と組み合わさって基礎編なのですが応用編と同じくらい難しい...(気がした)(木だけに)
Part3 応用編
応用編は流石にかなり大変でした...
1章にかかる時間は基礎編の倍以上(基礎が身についてないから？)だったので，$O(n)$で読めると思ったら大間違いです...
($O(n3)$という説が濃厚?)
14章 高度なデータ構造
標準ライブラリでサポートされた基礎的なデータ構造を応用して高度なデータ構造を学びます．
ここでは互いに素な集合(Union Find Tree)，領域探索(Range Search)について扱っています．
ここではlとrが出てくるのですが，ノードの子，親の話なのかそれとも左端，右端の話なのか勘違いしてやたら時間かかりました...
15章 高度なグラフアルゴリズム
これまでのデータ構造とアルゴリズムを応用した高度なアルゴリズムを学びます．
ここでは全点対間最短経路(All Pairs Shortest Path)，トポロジカルソート(Topological Sort)，関節点(Articulation Point)，木の直径(Diameter of a Tree)，最小全域木(Minimum Spanning Tree)について扱っています．
全点対間最短経路ではワーシャルフロイドのアルゴリズム，最小全域木ではクラスカルのアルゴリズムを紹介しています．
意味が一通りわかったけれども全く実装できる気がしない...後，classとかが出てきてC++の文法がちゃんとわからないとわけがわからなくなります(自分がそうだった)．
16章 計算幾何学
幾何学的な問題を解くための効率的なアルゴリズムとデータ構造を学びます．
ここでは幾何学に関する基本的な前提知識，直線の直行・平行判定(Orthogonal/Parallel)，射影(Projection)，反射(Reflection)，距離(Distance)，反時計回り(Counter-Clockwise)，線分の交差判定(Intersection)，線分の交点(Cross Point)，円と直線の交点(Cross Points of a Circle and a Line)，円と円の交点(Cross Point of Circles)，円の内包(Polygon-Point Containment)，凸包(Convex Hull)，線分交差問題(Segment Intersections Manhattan Geometry)について扱っています．
高校の数学(ⅡBまで)がわかっていれば大体すんなり理解できると思います(私は量が多い割にライブラリを作ってるだけなのでこの章は飛ばしました...)．
17章 動的計画法
基礎編で学んだ動的計画法に関連する典型的な問題を学びます．
ここではコイン問題(Coin Changing Problem)，ナップザック問題(Knapsack Problem)，最長増加部分列(Longest Increasing Subsequence)，最大正方形(Largest Square)，最大長方形(Largest Rectangle)，について扱っています．
最大長方形以外は割と簡単でした．
18章 整数論
整数に関する問題を扱います．
ここでは素数判定(Prime Numbers)，最大公約数(Greatest Common Divisor)，べき乗(Power)について扱っています．
素数判定ではエラトステネスの篩(The Sieve of Eratosthenes)が紹介されています．
ここはプログラミング経験者なら知っていそうなことばかりで「応用編...？」となってしまいました．
19章 ヒューリスティック探索
状態空間の中を体系的に探索するアルゴリズム，ヒューリスティック探索を学びます．
ここでは8クイーン問題(8 Queencs Problems)，8パズル(8 Puzzle)，15パズル(15 Puzzle)をについて扱っています．
めちゃくちゃ難しい(めちゃくちゃ難しい)です．
この記事で出てきた本
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
- 作者: 渡部有隆
- 出版社/メーカー: マイナビ出版
- 発売日: 2015/01/30
- メディア: Kindle版
- この商品を含むブログを見る
- 作者: 渡部有隆
- 出版社/メーカー: マイナビ出版
- 発売日: 2014/06/28
- メディア: Kindle版
- この商品を含むブログを見る
