最強最速アルゴリズムマー養成講座

2020年6月10日

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

ソフトバンククリエイティブ

著者：高橋直大

はじめに
準備篇

第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章動的計画法・メモ化
動的計画法の基本
　経路の探索
　探索を使った解法
　数学的解法
　メモ化再帰を使った解法
　動的計画法らしい解法
　ナップザック問題
　探索を使った解法
　メモ化再帰を使った解法
　動的計画法を使った解法
　動的計画法
会社の組織と給与
　問題の解説(探索)
　問題の解説(動的計画法)
仲の悪い隣人たち
　問題の解説(動的計画法)
キングとナイト
　問題の解説(動的計画法)
ビジネス握手
　問題の解説

第８章探索範囲を狭めるアルゴリズム
カラフルボックス&ボール
　問題の解説
貪欲法
　動的計画法は万能なのか
　なじみ深いようで意外と難しい「貪欲法」
株式投資シミュレーション
　問題の解説
バッチシステム
　問題の解説
自動車ローン
　問題の解説
数学的アプローチ円の国家群
　問題の解説
ハミルトン路
　問題の解説
上級編

第9章応用問題
バイナリフリップ
　問題の解説1
　問題の解説2
　問題の解説3
　問題の解説4
　問題の解説5
　この問題のまとめ
カントールの塵
　問題の解説
　この問題のまとめ
Not Two
　問題の解説
　この問題のまとめ
棒の切断
　問題の解説
　二分探索の終了条件について
　この問題のまとめ
無限数列
　問題の解説1
　問題の解説2
　問題の解説3
　問題の解説4
　問題の解説5
　問題の解説6
　この問題のまとめ
床板
　問題の解説1
　問題の解説2
　この問題のまとめ

第10章整列
連結判定
　単純な探索を利用した連結判定
　Union-Find
有向グラフと無向グラフ重み付きグラフ
　重み付きグラフ
　重み付きグラフの最短経路問題
ダイクストラ法
　ダイクストラ法
　優先度付きキュー
　これまで説明した動的計画法とダイクストラ法の大きな違い
最小全域木
　最小全域木
　愚直な全探索
　プリム法
　クラスカル法
辺にさまざまな情報があるグラフ
　辺にさまざまな情報があるグラフ
　頂点を増やすことによって簡単に表せるグラフ