プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

2015

PDFあり

目次

1章　オンラインジャッジを活用しよう

1.1 “プロコン”で勝つための勉強法

1.2 オンラインジャッジとは

1.3 ユーザ登録する

1.4 問題を閲覧する

問題の種類 / ファインダーから探す / コースから探す

1.5 問題を解く

問題文を読む / プログラムを提出する / 判定結果を確認する

1.6 マイページ

1.7 本書での活用方法

2.1 アルゴリズムとは

2.2 問題とアルゴリズムの例

2.3 疑似コード

2.4 アルゴリズムの効率

計算量の評価 / Ｏ表記法 / 計算量の比較

2.5 導入問題

3章　初等的整列

3.1 ソート：問題にチャレンジする前に

3.5 安定なソート

4章　データ構造

4.1 データ構造とは：問題にチャレンジする前に

4.2 スタック

4.3 キュー

4.5 標準ライブラリのデータ構造

4.6 データ構造の応用：面積計算

5章　探索

5.1 探索：問題にチャレンジする前に

5.5 標準ライブラリによる検索

5.6 探索の応用：最適解の計算

7章　高等的整列

7.5 標準ライブラリによる整列

sort

7.6 反転数

7.7 最小コストソート

8.1 木構造：問題にチャレンジする前に

8.2 根付き木の表現

8.4 木の巡回

8.5 木巡回の応用：木の復元

9章 二分探索木

9.1 二分探索木：問題にチャレンジする前に

9.2 二分探索木：挿入

9.3 二分探索木：探索

9.4 二分探索木：削除

9.5 標準ライブラリによる集合の管理

set / map

10.1 ヒープ：問題にチャレンジする前に

10.2 完全二分木

10.3 最大・最小ヒープ

10.4 優先度付きキュー

10.5 標準ライブラリによる優先度付きキュー

priority_queue

11.1 動的計画法とは：問題にチャレンジする前に

11.2 フィボナッチ数列

11.3 最長共通部分列

11.4 連鎖行列積

12章 グラフ

12.1 グラフ：問題にチャレンジする前に

12.2 グラフの表現

12.5 連結成分分解

13.1 重み付きグラフ：問題にチャレンジする前に

13.2 最小全域木

13.3 単一始点最短経路

14章 高度なデータ構造

14.1 互いに素な集合

14.2 領域探索

14.3 その他の問題

15章 高度なグラフアルゴリズム

15.1 全点対間最短経路

15.3 関節点

15.4 木の直径

15.6 その他の問題

16章 計算幾何学

16.1 幾何学的オブジェクトの基本要素と表現

点とベクトル / 線分と直線 / 円 / 多角形 / ベクトルの基本演算 / ベクトルの大きさ / Point・Vector クラス / ベクトルの内積：Dot Product / ベクトルの外積：Cross Product

16.2 直線の直交・平行判定

16.3 射影

16.4 反射

16.5 距離

２点間の距離：distance / 点と直線の距離 / 点と線分の距離 / 線分と線分の距離

16.6 反時計回り

16.7 線分の交差判定

16.8 線分の交点

16.9 円と直線の交点

16.10 円と円の交点

16.11 点の内包

16.12 凸包

16.13 線分交差問題

16.14 その他の問題

17.1 コイン問題

17.2 ナップザック問題

17.3 最長増加部分列

17.4 最大正方形

17.5 最大長方形

17.6 その他の問題

18章 整数論

18.2 最大公約数

18.3 べき乗

18.4 その他の問題

19.2 8パズル

19.3 15パズル

付録

参考文献