- 蟻本で項目をチェック。
- 螺旋本で該当事項を解いて基礎を理解。
- 蟻本で練習問題を解く。
(1)
2-1 すべての基本“全探索” ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥30
再帰関数‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥30
スタック‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥31
キュー‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥32
深さ優先探索‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥33
幅優先探索‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥36
特殊な状態の列挙‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥39
枝刈り‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥40
- ALDS1_5_A: Exhaustive Search
- 全探索、枝刈り有り全探索、DP
- ALDS1_3_A: Stack
- 逆ポーランド記法
- ALDS1_3_B: Queue
- ラウンドロビンスケジューリング
(2)
2-2 猪突猛進!“貪欲法”‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥42
硬貨の問題‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥42
区間の問題‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥43
辞書順最小の問題‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥45
その他の例題‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥47
簡単なので特になし
(3)
2-3 値を覚えて再利用“動的計画法” ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥52
探索のメモ化と動的計画法‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥52
漸化式を工夫する‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥58
計算問題に対するDP ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥66
- ALDS1_10_C: Longest Common Subsequence
- ALDS1_10_B: Matrix Chain Multiplication
- DPL_1_A: Coin Changing Problem
- DP (貪欲法では解けない)
- DPL_1_B: 0-1 Knapsack Problem
- DPL_1_D: Longest Increasing Subsequence
- 最後の問題<<<<
(4)
2-4 データを工夫して記憶する“データ構造” ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥69
木・二分木‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥69
プライオリティキューとヒープ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥69
二分探索木‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥75
Union-Find木‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥81
(5)
2-5 あれもこれも実は“グラフ” ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥87
グラフとは‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥87
グラフの表現‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥90
グラフの探索‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥93
最短路問題‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥94
最小全域木‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥99
応用問題‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥102
-
https://code-festival-2017-qualb.contest.atcoder.jp/tasks/code_festival_2017_qualb_c
- 二部グラフ
-
ALDS1_11_D: Connected Components
- DFS
-
ALDS1_12_A: Minimum Spanning Tree
- MST 最小全域木
- Prim
- Kruskal
-
ALDS1_12_B: Single Source Shortest Path I
- Dijkstra (O(V^2))
- Bellman-Ford
-
ALDS1_12_C: Single Source Shortest Path II
- priority_queue を使った実装
-
GRL_1_C: All Pairs Shortest Path
- Warshall-Floyd
-
Fliptile (POJ No.3279)
<--> ABC 018 D バレンタインデー
WA -
例題 3-2-5 Physics Experiment (POJ No.3684)
<--> AGC 013 C Ants on a Circle
WA -
例題 3-2-6 4 Values whose Sum is 0 (POJ No.2785)
<--> AOJ 0529