プログラミングコンテストチャレンジブック [第2版]

関連サイト

出版社による関連ページが公開されています。

• マイナビブックス

内容紹介

※当商品はページが画像化されたPDFです。テキストコピー、テキスト検索等ができませんので、あらかじめご了承ください。

プログラミングコンテストの問題を通してアルゴリズムのしくみや考え方を楽しく習得。

プログラミングコンテストにて世界トップレベルの成績を誇る著者たちが、コンテストで得た知識やノウハウを難易度別にまとめました。初心者が取り組めるアルゴリズムの基本問題から、世界中のプログラマを悩ませた難問まで。“プログラミング脳”を活性化するための問題を厳選して紹介します。

「プログラミングコンテスト」は上級者だけのものではありません。多くの場合は初級者向けの問題も用意され、幅広い参加者が楽しめるよう配慮されています。良い成績を収められなくてもプログラミング能力を向上させることにつながり、何より、楽しく充実した時間を過ごせます！

本書を読むにあたって必要なものは「基礎的なプログラミング能力」だけです。掲載したソースコードはC++ですが基本的な機能のみで記述しており、C++での開発経験がなくても読みやすいように配慮しました。

難易度別に分けて構成し、内容の多いトピックは難易度ごとに何度か扱っています。各トピックは説明と例題からなっています。

第2版となる本書では、４つの新しいトピック「平面・空間を扱う“計算幾何”」「工夫を凝らして賢く“探索”」「分けて解いてまとめる！“分割統治法”」「“文字列”を華麗に扱う」を追加した他、より理解を深めるための練習問題の紹介や、さらなる高みを目指す読者のために発展的内容の紹介を行い、より一層充実した内容になっています。

現役プログラマだけでなくプログラマを目指している方にもぜひ読んでいただきたい1冊です！

書誌情報

• 著者: 秋葉 拓哉, 岩田 陽一, 北川 宜稔
• 発行日: 2012-01-28
• 最終更新日: 2020-10-27
• バージョン: 1.19.0
• ページ数: 371ページ(PDF版換算)
• 対応フォーマット: PDF
• 出版社: マイナビ出版

対象読者

・あらゆるプログラマに！（プログラマを目指す方から現役の方まで）
・プログラミングコンテストに興味を持った方（プログラミングを始めて間もない方でも大丈夫！）
・C/C++のコードが読める方（開発経験がなくてもOK）
・「正確にできるだけ多く解く」ことを競うコンテスト（Google Code Jam、TopCoder、ACM/ICPCなど）に参加したい方。

著者について

秋葉 拓哉

2011年、東京大学大学院に入学。
プログラミングコンテストではiwiとして活躍。主な戦績はTopCoder Open 2011での7位など。

岩田 陽一

2011年、東京大学大学院に入学。
プログラミングコンテストではwataとして活躍。主な戦績はGoogle Code Jam 2009での3位など。

北川 宜稔

2011年、東京大学大学院に入学。
プログラミングコンテストではkita_masaとして活躍。主な戦績はICPC World Finals 2010での16位など。

目次

CHAPTER 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」
  • ハードルが上がった「くじびき」

CHAPTER 2 基礎からスタート！－－初級編

• 2-1 すべての基本“全探索”
  • 再帰関数
  • スタック
  • キュー
  • 深さ優先探索
  • 幅優先探索
  • 特殊な状態の列挙
  • 枝刈り
• 2-2 猪突猛進！“貪欲法”
  • 硬貨の問題
  • 区間の問題
  • 辞書順最小の問題
  • その他の例題
• 2-3 値を覚えて再利用“動的計画法”
  • 探索のメモ化と動的計画法
  • 漸化式を工夫する
  • 計算問題に対するDP
• 2-4 データを工夫して記憶する“データ構造”
  • 木・二分木
  • プライオリティキューとヒープ
  • 二分探索木
  • Union-Find木
• 2-5 あれもこれも実は“グラフ”
  • グラフとは
  • グラフの表現
  • グラフの探索
  • 最短路問題
  • 最小全域木
  • 応用問題
• 2-6 数学的な問題を解くコツ
  • ユークリッドの互除法
  • 素数に関する基本的なアルゴリズム
  • 余りの計算
  • べき乗を高速に計算する
• 2-7 GCJの問題に挑戦してみよう（1）
  • Minimum Scalar Product
  • Crazy Rows
  • Bribe the Prisoners
  • Millionaire
• [練習問題]

CHAPTER 3 ここで差がつく！－－中級編

• 3-1 値の検索だけじゃない！“二分探索”
  • ソート列から値を探す
  • 解を仮定し可能か判定
  • 最小値の最大化
  • 平均最大化
• 3-2 厳選！ 頻出テクニック（1）
  • しゃくとり法
  • 反転
  • 弾性衝突
  • 半分全列挙
  • 座標圧縮
• 3-3 さまざまなデータ構造を操ろう
  • セグメント木
  • Binary Indexed Tree
  • バケット法と平方分割
• 3-4 動的計画法を極める！
  • ビットDP
  • 行列累乗
  • データ構造を用いて高速化
• 3-5 水を流して問題を解く“ネットワークフロー”
  • 最大流
  • 最小カット
  • 二部マッチング
  • 一般マッチング
  • マッチング・辺カバー・安定集合・点カバー
  • 最小費用流
  • 応用問題
• 3-6 平面・空間を扱う“計算幾何”
  • 幾何の基本
  • ギリギリを考えよ
  • 平面走査
  • 凸包
  • 数値積分
• 3-7 GCJの問題に挑戦してみよう（2）
  • Numbers
  • No Cheating
  • Stock Charts
  • Watering Plants
  • Number Sets
  • Wi-fi Towers
• [練習問題]

CHAPTER 4 さらに極める！－－上級編

• 4-1 より複雑な数学的問題
  • 行列
  • modの世界
  • 数え上げ
  • 対称性のある数え上げ
• 4-2 ゲームの必勝法を編み出せ！
  • ゲームと必勝法
  • Nim
  • Grundy数
• 4-3 グラフマスターへの道
  • 強連結成分分解
  • 2-SAT
  • LCA
• 4-4 厳選！ 頻出テクニック（2）
  • スタックの利用
  • デックの利用
  • ダブリング
• 4-5 工夫を凝らして賢く探索
  • 枝狩り
  • A*とIDA*
• 4-6 分けて解いてまとめる！“分割統治法”
  • 列の分割統治法
  • ツリーの分割統治法
  • 平面の分割統治法
• 4-7 文字列を華麗に扱う
  • 文字列に対する動的計画法
  • 文字列検索
  • 接尾辞配列
• 4-8 GCJの問題に挑戦してみよう（3）
  • Mine Layer
  • Year of More Code Jam
  • Football Team
  • Endless Knight
  • The Year of Code Jam
• [練習問題]

本書で扱わなかった発展的トピック

本書に掲載した問題リスト

索引

参考文献