最終更新:2010-09-01 (水) 09:56:17 (3674d)  

参考図書/プログラミングコンテストチャレンジブック
Top / 参考図書 / プログラミングコンテストチャレンジブック

 


http://book.mycom.co.jp/book/978-4-8399-3199-5/978-4-8399-3199-5.shtml

目次

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 値を覚えて再利用“動的計画法

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 動的計画法を極める!

3-6 水を流して問題を解く“ネットワークフロー?

  • 最大流?
  • 最小カット?
  • 二部マッチング?
  • 一般マッチング?
  • マッチング?辺カバー?安定集合?点カバー?
  • 最小費用流?
  • 練習問題

3-7 GCJの問題に挑戦してみよう(2)

  • Numbers
  • No Cheating
  • Stock Charts
  • Watering Plants
  • Number Sets
  • Wi-fi Towers

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

4-1 より複雑な数学的問題

  • 行列
  • mod?の世界
  • 数え上げ?
  • 対称性?のある数え上げ

4-2 ゲームの必勝法を編み出せ!

4-3 グラフマスターへの道

  • 強連結成分分解?
  • 2-SAT?
  • LCA?

4-4 厳選! 頻出テクニック(2)

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

参考