プログラミングコンテストの本を書きました
id:wata_orz や kita_masa と少しずつ書いていたプログラミングコンテストの本がようやく完成し,発売間近となりました.
Google Code Jam,TopCoder,ICPC, 情報オリンピックなどのような,問題を解くプログラミングコンテストの,特にアルゴリズムに関する話題に焦点を絞った本です.全探索や動的計画法などの基礎的な部分から始まりますが,ネットワークフローや数論などのレベルの高い話題まで扱っており,幅広いレベルの人に楽しんでもらえると思います.
また,アルゴリズムの解説だけでなく,章の中で POJ (PKU Judge Online) の問題を扱い,章末で Google Code Jam の問題を扱っています.特に,POJ の問題には基本的に解説がないので,POJ のお供として使うのも良いんじゃないかと思います.
文章には拙いところも多いと思いますが,我々でないと書けないような内容にできたと思います.是非よろしくお願いします.
以下,目次です.
- 1 いざチャレンジ! でもその前に−−準備編
- 1-1 プログラミングコンテストって何?
- 1-2 どんなコンテストがあるの?
- 1-3 この本での進め方
- 本書で扱う内容について
- 使用する言語について
- 問題の扱いについて
- プログラムについて
- さらなる練習方法
- 1-4 どうやって解答を提出するの?
- POJへの提出の仕方
- GCJへの提出の仕方
- 1-5 効率的なアルゴリズムを目指すには
- 計算量って何だろう
- 実行時間について
- 1-6 気楽にウォーミングアップ
- まずは簡単な問題から
- POJの問題「Ants」
- ハードルが上がった「くじびき」
- 2 基礎からスタート!−−初級編
- 2-2 猪突猛進!“貪欲法”
-
- 硬貨の問題
- 区間スケジューリング問題
- Best Cow Line
- Saruman's Army
- Fence Repair
- 2-3 値を覚えて再利用“動的計画法”
- 探索のメモ化と動的計画法
- 漸化式を工夫する
- 計算問題に対するDP
- 2-4 データを工夫して記憶する“データ構造”
- 木・二分木
- プライオリティキューとヒープ
- 二分探索木
- Union-Find木
- 2-5 あれもこれも実は“グラフ”
- グラフとは
- グラフの表現
- グラフの探索
- 最短路問題
- 最小全域木
- 練習問題
- 2-6 GCJの問題に挑戦してみよう(1)
- Minimum Scalar Product
- Crazy Rows
- Bribe the Prisoners
- Millionaire
-
- 3 ここで差がつく!−−中級編
-
- 3-1 数学的な問題を解くコツ
- ユークリッドの互除法
- 素数に関する基本的なアルゴリズム
- 余りの計算
- べき乗を高速に計算する
- 3-2 値の検索だけじゃない!“二分探索”
- ソート列から値を探す
- 解を仮定し可能か判定
- 最小値の最大化
- 平均最大化
- 3-3 厳選! 頻出テクニック(1)
- しゃくとり法
- 反転
- 弾性衝突
- 半分全列挙
- 座標圧縮
- 3-4 さまざまなデータ構造を操ろう
- セグメント木
- Binary Indexed Treeとは
- バケット法と平方分割
- 3-5 動的計画法を極める!
- ビットDP
- 行列累乗
- データ構造を用いて高速化
- 3-6 水を流して問題を解く“ネットワークフロー”
- 最大流
- 最小カット
- 二部マッチング
- 一般マッチング
- マッチング・辺カバー・安定集合・点カバー
- 最小費用流
- 練習問題
- 3-7 GCJの問題に挑戦してみよう(2)
- Numbers
- No Cheating
- Stock Charts
- Watering Plants
- Number Sets
- Wi-fi Towers
- 3-1 数学的な問題を解くコツ
- 4 さらに極める!−−上級編