プログラミングコンテストの本を書きました

id:wata_orz や kita_masa と少しずつ書いていたプログラミングコンテストの本がようやく完成し,発売間近となりました.

Google Code Jam,TopCoderICPC, 情報オリンピックなどのような,問題を解くプログラミングコンテストの,特にアルゴリズムに関する話題に焦点を絞った本です.全探索や動的計画法などの基礎的な部分から始まりますが,ネットワークフローや数論などのレベルの高い話題まで扱っており,幅広いレベルの人に楽しんでもらえると思います.

また,アルゴリズムの解説だけでなく,章の中で POJ (PKU Judge Online) の問題を扱い,章末で Google Code Jam の問題を扱っています.特に,POJ の問題には基本的に解説がないので,POJ のお供として使うのも良いんじゃないかと思います.

文章には拙いところも多いと思いますが,我々でないと書けないような内容にできたと思います.是非よろしくお願いします.

以下,目次です.


  • 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-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 
    • 領域木 
    • 完全マッチングの個数 
    • もっと高速な漸化式の計算 
    • さまざまなグラフに対する最大流 
    • 高速なフローアルゴリズム 
    • さまざまなグラフに対する最小費用流 
    • 計算誤差 
    • 多倍長演算