アルゴリズム

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

渡部有隆
Ozy(協力)
秋葉拓哉(協力)

マイナビ

はじめよう、アルゴリズムコレクション

  • 本書の概要
  • 教員の皆さまへ
  • オンラインジャッジを活用しよう
  • 本書で扱う問題
  • 本書の活用方法

Part 1 [準備編]プロコンで勝つための勉強法
1章 オンラインジャッジを活用しよう

  • 1,1 “プロコン”で勝つための勉強法
  • 1.2 オンラインジャッジとは
  • 1.3 ユーザ登録する
  • 1.4 問題を閲覧する
    • 1.4.1 問題の種類
    • 1.4.2 ファインダーから探す
    • 1.4.3 コースから探す
  • 1.5 問題を解く
    • 1.5.1 問題文を読む
    • 1.5.2 プログラムを提出する
    • 1.5.3 判定結果を確認する
  • 1.6 マイページ
  • 1.7 本書での活用方法

Part 2 [基礎編]プロコンのためのアルゴリズムとデータ構造
2章 アルゴリズムと計算量

  • 2.1 アルゴリズムとは
  • 2.2 問題とアルゴリズムの例
  • 2.3 擬似コード
  • 2.4 アルゴリズムの効率
    • 2.4.1 計算量の評価
    • 2.4.2 O表記法
    • 2.4.3 計算量の比較
  • 2.5 導入問題

3章 初等的整列

  • 3.1 ソート:問題にチャレンジする前に
  • 3.2 挿入ソート
  • 3.3 バブルソート
  • 3.4 選択ソート
  • 3.5 安定なソート
  • 3.6 シェルソート

4章 データ構造

  • 4.1 データ構造とは:問題にチャレンジする前に
  • 4.2 スタック
  • 4.3 キュー
  • 4.4 連結リスト
  • 4.5 標準ライブラリのデータ構造
    • 4.5.1 C++の標準ライブラリ
    • 4.5.2 stack
    • 4.5.3 queue
    • 4.5.4 vector
    • 4.5.5 list
  • 4.6 データ構造の応用:面積計算

5章 探索

  • 5.1 探索:問題にチャレンジする前に
  • 5.2 線形探索
  • 5.3 二分探索
  • 5.4 ハッシュ
  • 5.5 標準ライブラリによる検索
    • 5.5.1 イテレータ
    • 5.5.2 lower_bound
  • 5.6 探索の応用:最適解の計算

6章 再帰・分割統治法

  • 6.1 再帰と分割統治:問題にチャレンジする前に
  • 6.2 全探索
  • 6.3 コッホ曲線

7章 高等的整列

  • 7.1 マージソート
  • 7.2 パーティション
  • 7.3 クイックソート
  • 7.4 計算ソート
  • 7.5 標準ライブラリによる整列
    • 7.5.1 sort
  • 7.6 反転数
  • 7.7 最小コストソート

8章 木

  • 8.1 木構造:問題にチャレンジする前に
  • 8.2 根付け木の表現
  • 8.3 二分木の表現
  • 8.4 木の巡回
  • 8.5 木巡回の応用:木の復元

9章 二分探索木

  • 9.1 二分探索木:問題にチャレンジする前に
  • 9.2 二分探索木:挿入
  • 9.3 二分探索木:探索
  • 9.4 二分探索木:削除
  • 9.5 標準ライブラリによる集合の管理
    • 9.5.1 set
    • 9.5.2 map

10章ヒープ

  • 10.1 ヒープ:問題にチャレンジする前に
  • 10.2 完全二分木
  • 10.3 最大・最小ヒープ
  • 10.4 優先度付きキュー
  • 10.5 標準ライブラリによる優先度付きキュー
    • 10.5.1 priority_queue

11章 動的計画法

  • 11.1 動的計画法とは:問題にチャレンジする前に
  • 11.2 フィボナッチ数列
  • 11.3 最長共通部分列
  • 11.4 連鎖行列積

12章 グラフ

  • 12.1 グラフ:問題にチェレンジする前に
    • 12.1.1 グラフの種類
    • 12.1.2 グラフの表記と用語
    • 12.1.3 グラフの基本的なアルゴリズム
  • 12.2 グラフの表現
  • 12.3 深さ優先探索
  • 12.4 幅優先探索
  • 12.5 連結成分

13章 重み付きグラフ

  • 13.1 重み付きグラフ:問題にチャレンジする前に
  • 13.2 最小全域木
  • 13.3 単一始点最短経路

Part 3 [応用編]プロコン必携ライブラリ
14章 高度なデータ構造

  • 14.1 互いに素な集合
  • 14.2 領域探索
  • 14.3 その他の問題

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

  • 15.1 全点対間最短経路
  • 15.2 トポロジカルソート
  • 15.3 関節点
  • 15.4 木の直径
  • 15.5 最小全域木
  • 15.6 その他の問題

16章 計算幾何学

  • 16.1 幾何学的オブジェクトの基本要素と表現
    • 16.1.1 点とベクトル
    • 16.1.2 線分と直線
    • 16.1.3 円
    • 16.1.4 多角形
    • 16.1.5 ベクトルの基本演算
    • 16.1.6 ベクトルの大きさ
    • 16.1.7 Point・Vectorクラス
    • 16.1.8 ベクトルの内積
    • 16.1.9 ベクトルの外積
  • 16.2 直線の直交・平行判定
  • 16.3 射影
  • 16.4 反射
  • 16.5 距離
    • 16.5.1 2点間の距離
    • 16.5.2 点と直線の距離
    • 16.5.3 点と線分の距離
    • 16.5.4 線分と線分の距離
  • 16.6 反時計回り
  • 16.7 線分の交差判定
  • 16.8 線分の交点
  • 16.9 円と直線の交点
  • 16.10 円と円の交点
  • 16.11 点の内包
  • 16.12 凸包
  • 16.13 線分交差問題
  • 16.14 その他の問題

17章 動的計画法

  • 17.1 コイン問題
  • 17.2 ナップザック問題
  • 17.3 最長増加部分列
  • 17.4 最大正方形
  • 17.5 最大長方形
  • 17.6 その他の問題

18章 整数論

  • 18.1 素数判定
  • 18.2 最大公約数
  • 18.3 べき乗
  • 18.4 その他の問題

19章 ヒューリスティック探索

  • 19.1 8クイーン問題
  • 19.2 8パズル
  • 19.3 15パズル

付録

  • 本書で獲得できるスキルの一覧
  • プログラミングコンテストの過去問にチャレンジ!
  • 参考文献

索引