アルゴリズム

最強最速アルゴリズマー養成講座 プログラミングコンテストTopCoder攻略ガイド

高橋直大
SoftBank Creative

はじめに

準備篇

第1章 プログラミングコンテストって?

  • プログラミングコンテストとは?
  • コンテストに参加する利点
  • 初心プログラマーに最適な競技プログラミング

第2章 TopCoderに参加しよう
TopCoderのシステム

  • TopCoder SRMとは
  • SRMの構成
  • SRMのレーティング

TopCoderへの登録方法

  • TopCoderへの登録

SRMへチャレンジ

  • SRMへの参加方法

SRM参加のポイント

  • 問題の読み方
  • 便利な補助ツール

第3章 最低限必要な知識をつけよう!
絶対に必要なプログラミング能力

  • プログラミングコンテストに必要な知識
  • if、else
  • for
  • 配列
  • 提出フォーマット

追加で必要なプログラミング知識

  • 覚えておくと便利な知識
  • ソート
  • 文字列
  • 連想配列

初級編

第4章 シミュレーション
キウイジュース

  • 問題の解説
  • 応用技1
  • 応用技2

第5章 全探索
みんなが楽しいパーティ

  • 問題の解説
  • 応用技
  • 数学的問題に対する全探索

暗号文

  • 問題の解説
  • 応用技

おもしろい数学

  • 問題の解説
  • 応用技
  • さまざまな種類の全探索

山本山

  • 問題の解説
  • 強固なイメージをもつための「グラフ」

友達の数

  • 問題の解説

さまざまなタイプの全探索

  • さなざなばタイプの探索
  • 深さ優先探索と幅優先探索
  • たいていの物事はグラフに変換できる
  • ダイクストラ法
  • 枝刈り
  • 探索の実装
  • 深さ優先探索のイメージ
  • 幅優先探索のイメージ
  • データ構造
  • 再帰関数
  • 深さ優先探索の実装
  • 幅優先探索の実装
  • 深さ優先探索と幅優先探索の違い

壊れたロボット

  • 問題の解説

迷路づくり名人

  • 問題の解説
  • bit全探索

ナンバーマジック

  • 問題の解説1
  • 問題の解説2
  • 問題の解説3

中級編

第6章 計算量
計算時間、メモリ使用量を予測するために

  • プログラム実行に関する制約事項と計算量
  • 時間計算量
  • 計算量の計算が難しいケース
  • 計算量の大きい関数を呼びだしている場合
  • 空間計算量

第7章 動的計画法・メモ化
動的計画法の基本

  • 経路の探索
  • 探索を使った解法
  • 数学的解法
  • メモ化再帰を使った解法
  • 動的計画法らしい解法
  • ナップザック問題
  • 探索を使った解法
  • メモ化再帰を使った解法
  • 動的計画法を使った解法
  • 動的計画法

会社の組織と給与

  • 問題の解説(探索)
  • 問題の解説(動的計画法)

仲の悪い隣人たち

  • 問題の解説(動的計画法)

キングとナイト

  • 問題の解説(動的計画法)

ビジネス握手

  • 問題の解説

第8章 探索範囲を狭めるアルゴリズム
カラフルボックス&ボール

  • 問題の解説

貪欲法

  • 動的計画法は万能なのか
  • なじみ深いようで意外と難しい「貪欲法」

株式投資シミュレーション

  • 問題の解説

バッチシステム

  • 問題の解説

自動車ローン

  • 問題の解説

数学的アプローチ円の国家群

  • 問題の解説

ハミルトン路

  • 問題の解説

上級編

第9章 応用問題
バイナリフリップ

  • 問題の解説1
  • 問題の解説2
  • 問題の解説3
  • 問題の解説4
  • 問題の解説5
  • この問題のまとめ

カントールの塵

  • 問題の解説
  • この問題のまとめ

Not Two

  • 問題の解説
  • この問題のまとめ

棒の切断

  • 問題の解説
  • 二分探索の終了条件について
  • この問題のまとめ

無限数列

  • 問題の解説1
  • 問題の解説2
  • 問題の解説3
  • 問題の解説4
  • 問題の解説5
  • 問題の解説6
  • この問題のまとめ

床板

  • 問題の解説1
  • 問題の解説2
  • この問題のまとめ

第10章 整列
連結判定

  • 単純な探索を利用した連結判定
  • Union-Find

有向グラフと無向グラフ重み付きグラフ

  • 重み付きグラフ
  • 重み付きグラフの最短経路問題

ダイクストラ法

  • ダイクストラ法
  • 優先度付きキュー
  • これまで説明した動的計画法とダイクストラ法の大きな違い

最小全域木

  • 最小全域木
  • 愚直な全探索
  • プリム法
  • クラスカル法

辺にさまざまな情報があるグラフ

  • 辺にさまざまな情報があるグラフ
  • 頂点を増やすことによって簡単に表せるグラフ

第11章 数学問題対策
素数

  • 素数
  • 素数判定
  • O√nの方針
  • その他の素数判定法
  • 素数列挙

最大公約数、最小公倍数

  • 最大公約数、最小公倍数
  • 愚直な実装
  • ユークリッドの互除法
  • 拡張ユークリッドの互除法

索引
TopCoder問題一覧
カテゴリ別問題一覧
難易度別問題一覧