関連サイト
本書の関連ページが用意されています。
内容紹介
本書はプログラミングコンテストの問題を攻略するための「アルゴリズムとデータ構造」を体得するための参考書です。初級者が体系的にアルゴリズムとデータ構造の基礎を学ぶことができる入門書となっています。
プログラミングコンテストでは、高い数理的能力で上位ランクを得ることができますが、多くの入門者においては基礎アルゴリズムの応用が目の前の問題の攻略に繋がります。つまり、基礎対策をすることでランクを上げ（問題が解けて）コンテストを楽しむことができます。
基礎対策と言っても辛い勉強ではありません。そこには、体得したスキルで問題を解いていく楽しみ、応用する楽しみ、アルゴリズムとデータ構造を網羅的に「コレクション」していく楽しみがあります。このような楽しみを体感しながら学習・対策できるように、本書ではコンテストの競技システムに類似した、オンラインジャッジと呼ばれるプログラムの自動採点システムを通してアルゴリズムとデータ構造を獲得していきます。
本書の内容はAIZU ONLINE JUDGEでチャレンジすることが可能です！
書誌情報
- 著者: 渡部有隆, Ozy(協力), 秋葉 拓哉(協力)
- 発行日: 2015-01-30 (紙書籍版発行日: 2015-01-30)
- 最終更新日: 2015-01-30
- バージョン: 1.0.0
- ページ数: 480ページ(PDF版換算)
- 対応フォーマット: PDF
- 出版社: マイナビ出版
対象読者
プログラミング入門書を読み終えた方、プログラミングコンテストで勝ちたい・上位にあがりたい方
著者について
渡部有隆
1979 年生まれ。コンピュータ理工学博士。会津大学 コンピュータ理工学部 情報システム学部門 准教授。専門はビジュアルプログラミング言語。AIZU ONLINE JUDGE 開発者。http://web-ext.u-aizu.ac.jp/~yutaka/
Ozy
学習塾経営の傍ら研究・開発を行う。主に組み合わせ最適化、可視化の分野を研究。著書に『ショートコーディング 職人達の技法』、翻訳書に『世界で闘うプログラミング力を鍛える150問』（以上マイナビ刊）がある。
秋葉 拓哉
2011年東京大学大学院に入学。プログラミングコンテストではiwi として活躍。TopCoder レーティングでの最高は世界4 位（2013年）。共著に『プログラミングコンテストチャレンジブック 第2版』、監訳に『世界で闘うプログラミング力を鍛える150問』（以上マイナビ刊）がある。
目次
Part 1 [準備編]プロコンで勝つための勉強法
1章 オンラインジャッジを活用しよう
- 1.1 “プロコン”で勝つための勉強法
- 1.2 オンラインジャッジとは
- 1.3 ユーザ登録する
- 1.4 問題を閲覧する
- 問題の種類 / ファインダーから探す / コースから探す
- 1.5 問題を解く
- 問題文を読む / プログラムを提出する / 判定結果を確認する
- 1.6 マイページ
- 1.7 本書での活用方法
Part 2 [基礎編]プロコンのためのアルゴリズムとデータ構造
2章 アルゴリズムと計算量
- 2.1 アルゴリズムとは
- 2.2 問題とアルゴリズムの例
- 2.3 疑似コード
- 2.4 アルゴリズムの効率
- 計算量の評価 / Ｏ表記法 / 計算量の比較
- 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 標準ライブラリのデータ構造
- C++の標準ライブラ / stack / queue / vector / list
- 4.6 データ構造の応用：面積計算
5章 探索
- 5.1 探索：問題にチャレンジする前に
- 5.2 線形探索
- 5.3 二分探索
- 5.4 ハッシュ
- 5.5 標準ライブラリによる検索
- イテレータ / lower bound
- 5.6 探索の応用：最適解の計算
6章 再帰・分割統治法
- 6.1 再帰と分割統治：問題にチャレンジする前に
- 6.2 全探索
- 6.3 コッホ曲線
7章 高等的整列
- 7.1 マージソート
- 7.2 パーティション
- 7.3 クイックソート
- 7.4 計数ソート
- 7.5 標準ライブラリによる整列
- 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 標準ライブラリによる集合の管理
- set / map
10章ヒープ
- 10.1 ヒープ：問題にチャレンジする前に
- 10.2 完全二分木
- 10.3 最大・最小ヒープ
- 10.4 優先度付きキュー
- 10.5 標準ライブラリによる優先度付きキュー
- priority_queue
11章 動的計画法
- 11.1 動的計画法とは：問題にチャレンジする前に
- 11.2 フィボナッチ数列
- 11.3 最長共通部分列
- 11.4 連鎖行列積
12章 グラフ
- 12.1 グラフ：問題にチャレンジする前に
- 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 幾何学的オブジェクトの基本要素と表現
- 点とベクトル / 線分と直線 / 円 / 多角形 / ベクトルの基本演算 / ベクトルの大きさ / 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章 動的計画法
- 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パズル