アルゴリズム

プログラミングコンテストチャレンジブック[第2版]
- 問題解決のアルゴリズム活用力とコーディングテクニックを鍛える -

秋葉拓哉
岩田陽一
北川宜稔
マイナビ

初版の目次

1 いざチャレンジ!でもその前に-準備編

  • 1-1 プログラミングコンテストって何?
  • 1-2 どんなコンテストがあるの?
    • 世界規模のコンテスト-Google Code Jam(GCJ)
    • 上位ランクを目指せ!-TopCoder
    • 最も歴史のあるコンテスト-ACM/ICPC
    • 中学・高校生向けの情報オリンピック-JOI/IOI
    • Web状で自動採点-オンラインジャッジ
  • 1-3 この本での進め方
    • 本書で扱う内容について
    • 使用する言語について
    • 問題の扱いについて
    • プログラムについて
    • さらなる練習法
  • 1-4 どうやって解答を提出するの?
    • POJへの提出の仕方
    • GCJへの提出の仕方
  • 1-5 効率的なアルゴリズムを目指すには
    • 計算量って何だろう
    • 実行時間について
  • 1-6 気軽にウォーミングアップ
  • まずは簡単な問題から
  • POJ問題「Ants」
  • ハードルが上がった「くじびき」

2 基礎からスタート!-初級編

  • 2-1 すべての基本"全探索”
    • 再帰関数
    • スタック
    • キュー
    • 深さ優先探索
    • 幅優先探索
    • 特殊な状態の列挙
    • 枝刈り
  • 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

4 さらに極める!-上級編

  • 4-1 より複雑な数学的問題
    • 行列
    • modの世界
    • 数え上げ
    • 対称性のある数え上げ
    • 4-2 ゲームの必勝法を編み出せ!
    • ゲームと必勝法
    • Nim
    • Grundy数
  • 4-3 グラフマスターへの道
    • 強連結成分分解
    • 2-SAT
    • LCA
  • 4-4 厳選!頻出テクニック(2)
    • スタックの利用
    • デックの利用
    • LogStepDP
  • 4-5 GCJの問題に挑戦してみよう(3)
    • Mine Layer
    • Year of More Code Jam
    • Football Team
    • Endless Knight
    • The Year of Code Jam

本書に掲載した問題リスト
索引
参考文献

column

  • スタック領域とヒープ領域
  • アルゴリズムの証明
  • ハフマン符号
  • memset
  • 全探索の書き方
  • 初期化
  • いろいろなDP
  • 再利用の仕方
  • lower_bound
  • 平衡二分木
  • 証明や法則などについて
  • 収束判定
  • Sparse Table
  • 領域木
  • 完全マッチングの個数
  • もっと高速な漸化式の計算
  • さまざまなグラフに対する最大流
  • 高速なフローアルゴリズム
  • さまざまなグラフに対する最小費用流
  • 計算誤差
  • 多倍長演算