競技プログラミングのソース置場   WEB+DB 115   AOJ本   PAST本   けんちょん本   アリ本   ライブラリ   AOJ   ABC   ARC   PAST

「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」の読書メモで、
解いた問題のソースや、解法をまとめてます。

サポートサイト


2章 アルゴリズムと計算量

Q001 046ページ 導入問題(ALDS1_1_D: Maximum Profit)


3章 初等的整列

Q002 054ページ 挿入ソート(ALDS1_1_A: Insertion Sort)
Q003 060ページ バブルソート(ALDS1_2_A: Bubble Sort)
Q004 065ページ 選択ソート(ALDS1_2_B: Selection Sort)
Q005 070ページ 安定なソート(ALDS1_2_C: Stable Sort)
Q006 074ページ シェルソート(ALDS1_2_D: Shell Sort)


4章 データ構造

Q007 082ページ スタック(ALDS1_3_A: Stack)
Q008 086ページ キュー(ALDS1_3_B: Queue)
Q009 094ページ 連結リスト(ALDS1_3_C: Doubly Linked List)
Q010 114ページ データ構造の応用:面積計算(ALDS1_3_D: Areas on the Cross-Section Diagram)


5章 探索

Q011 119ページ 線形探索(ALDS1_4_A: Linear Search)
Q012 122ページ 二分探索(ALDS1_4_B: Binary Search)
Q013 126ページ ハッシュ(ALDS1_4_C: Dictionary)
Q014 136ページ 探索の応用:最適解の計算(ALDS1_4_D: Allocation)


6章 再帰・分割統治法

Q015 142ページ 全探索(ALDS1_5_A: Exhaustive Search)
作成中 Q016 146ページ コッホ曲線(ALDS1_5_C: Koch Curve)


7章 高等的整列

Q017 152ページ マージソート(ALDS1_5_B: Merge Sort)
Q018 158ページ パーティション(ALDS1_6_B: Partition)
Q019 163ページ クイックソート(ALDS1_6_C: Quick Sort)
Q020 168ページ 計数ソート(ALDS1_6_A: Counting Sort)
Q021 175ページ 反転数(ALDS1_5_D: The Number of Inversions)
Q022 179ページ 最小コストソート(ALDS1_6_D: Minimum Cost Sort)


8章 木

Q023 188ページ 根付き木の表現(ALDS1_7_A: Rooted Trees)
Q024 193ページ 二分木の表現(ALDS1_7_B: Binary Tree)
Q025 198ページ 木の巡回(ALDS1_7_C: Tree Walk)
Q026 203ページ 木巡回の応用:木の復元(ALDS1_7_D: Reconstruction of the Tree)


9章 二分探索木

Q027 209ページ 二分探索木:挿入(ALDS1_8_A: Binary Search Tree I)
Q028 214ページ 二分探索木:探索(ALDS1_8_B: Binary Search Tree II)
Q029 217ページ 二分探索木:削除(ALDS1_8_C: Binary Search Tree III)


10章 ヒープ

Q030 234ページ 完全二分木(ALDS1_9_A: Complete Binary Tree)
Q031 236ページ 最大・最小ヒープ(ALDS1_9_B: Maximum Heap)
Q032 240ページ 優先度付きキュー(ALDS1_9_C: Priority Queue)


11章 動的計画法

Q033 249ページ フィボナッチ数列(ALDS1_10_A: Fibonacci Number)
Q034 253ページ 最長共通部分列(ALDS1_10_C: Longest Common Subsequence)
Q035 257ページ 連鎖行列積(ALDS1_10_B: Matrix Chain Multiplication)


12章 グラフ

Q036 269ページ グラフの表現(ALDS1_11_A: Graph)
Q037 273ページ 深さ優先探索(ALDS1_11_B: Depth First Search)
Q038 282ページ 幅優先探索(ALDS1_11_C: Breadth First Search)
Q039 287ページ 連結成分(ALDS1_11_D: Connected Components)


13章 重み付きグラフ

Q040 296ページ 最小全域木(ALDS1_12_A: Minimum Spanning Tree)
Q041 302ページ 単一始点最短経路(ALDS1_12_B: Single Source Shortest Path I)
Q042 309ページ 単一始点最短経路 II(ALDS1_12_C: Single Source Shortest Path II)


14章 高度なデータ構造

Q043 318ページ 互いに素な集合(DSL_1_A: Disjoint Set: Union Find Tree)
Q044 324ページ 領域探索(DSL_2_C: Range Search (kD Tree))

その他の問題
Q045 DSL_2_A: Range Minimum Query
Q046 DSL_2_B: Range Sum Query


15章 高度なグラフアルゴリズム

Q047 336ページ 全点対間最短経路(GRL_1_C: All Pairs Shortest Path)
Q048 342ページ トポロジカルソート(GRL_4_B: Topological Sort)
Q049 348ページ 関節点(GRL_3_A: Articulation Point)
Q050 353ページ 木の直径(GRL_5_A: Diameter of a Tree)
Q051 358ページ 最小全域木(GRL_2_A: Minimum Spanning Tree)

その他の問題
Q052 GRL_1_B: Single Source Shortest Path (Negative Edges)
Q053 GRL_3_B: Bridge
Q054 GRL_3_C: Strongly Connected Components
Q055 GRL_2_B: Minimum-Cost Arborescence
Q056 GRL_6_B: Maximum Flow
Q057 GRL_7_A: Bipartite Matching


16章 計算幾何学

Q058 374ページ 直線の直交・平行判定(CGL_2_A: Parallel/Orthogonal)
Q059 376ページ 射影(CGL_1_A: Projection)
Q060 378ページ 反射(CGL_1_B: Reflection)
Q061 380ページ 距離(CGL_2_D: Distance)
Q062 384ページ 反時計回り(CGL_1_C: Counter-Clockwise)
Q063 387ページ 線分の交差判定(CGL_2_B: Intersection)
Q064 390ページ 線分の交点(CGL_2_C: Cross Point)
Q065 393ページ 円と直線の交点(CGL_7_D: Cross Points of a Circle and a Line)
Q066 396ページ 円と円の交点(CGL_7_E: Cross Points of Circles)
Q067 398ページ 点の内包(CGL_3_C: Polygon-Point Containment)
Q068 401ページ 凸包(CGL_4_A: Convex Hull)
Q069 405ページ 線分交差問題(CGL_6_A: Segment Intersections: Manhattan Geometry)

その他の問題
作成中 Q070 CGL_5_A: Closest Pair
作成中 Q071 CGL_4_B: Diameter of a Convex Polygon
作成中 Q072 CGL_4_C: Convex Cut


17章 動的計画法

Q073 412ページ コイン問題(DPL_1_A: Coin Changing Problem)
Q074 416ページ ナップザック問題(DPL_1_B: 0-1 Knapsack Problem)
Q075 421ページ 最長増加部分列(DPL_1_D: Longest Increasing Subsequence)
Q076 425ページ 最大正方形(DPL_3_A: Largest Square)
Q077 428ページ 最大長方形(DPL_3_B: Largest Rectangle)

その他の問題
Q078 DPL_1_C: Knapsack Problem
Q079 DPL_1_E: Edit Distance (Levenshtein Distance)
Q080 DPL_2_A: Traveling Salesman Problem
作成中 Q081 DPL_2_B: Chinese Postman Problem


18章 整数論

Q082 436ページ 素数判定(ALDS_1_C: Prime Numbers)
Q083 441ページ 最大公約数(ALDS1_1_B: Greatest Common Divisor)
Q084 445ページ べき乗(NTL_1_B: Power)

その他の問題
Q085 NTL_1_A: Prime Factorize
Q086 NTL_1_C: Least Common Multiple
Q087 NTL_1_D: Euler's Phi Function
作成中 Q088 NTL_1_E: Extended Euclid Algorithm


19章 ヒューステリック探索

Q089 450ページ 8クイーン問題(ALDS1_13_A: 8 Queens Problem)
Q090 455ページ 8パズル(ALDS1_13_B: 8 Puzzle)
Q091 461ページ 15パズル(ALDS1_13_C: 15 Puzzle)


プログラミングコンテストの過去問にチャレンジ!

■ 整列・探索
作成中 Q092 1187 ICPC Ranking
作成中 Q093 2104 Country Road
作成中 Q094 0529 Darts
作成中 Q095 0539 Pizza

■ データ構造
作成中 Q096 1173 The Balance of the World
作成中 Q097 0558 Cheese
作成中 Q098 0301 Baton Relay Game
作成中 Q099 0282 Programming Contest
作成中 Q100 2170 Marked Ancestor Union-Find
作成中 Q101 1330 Never Wait for Weights Union-Find

■ 再帰・分割統治
作成中 Q102 0507 Square
作成中 Q103 0525 Osenbei
作成中 Q104 2057 The Closest Circle

■ グラフ
作成中 Q105 0508 String With Rings
作成中 Q106 1166 Amazing Mazes
作成中 Q107 2511 Sinking island
作成中 Q108 0519 Worst Sportswriter
作成中 Q109 0526 Boat Travel
作成中 Q110 1182 Railway Connection
作成中 Q111 1162 Discrete Speed
作成中 Q112 1196 Bridge Removal
作成中 Q113 2224 Save your cat

■ 動的計画法
作成中 Q114 2272 Cicada
作成中 Q115 1167 Pollock's conjecture
作成中 Q116 2090 Repeated Subsequences
作成中 Q117 0561 Books
作成中 Q118 2431 House Moving
作成中 Q119 0310 Frame

■ 計算幾何学
作成中 Q120 1053 Accelerated Railgan
作成中 Q121 2003 Railroad Conflict
作成中 Q122 1157 Roll-A-Big-Ball
作成中 Q123 1298 Separate points
作成中 Q124 1047 Crop Circle
作成中 Q125 1247 Monster Trap

■ 整数
作成中 Q126 1257 Sum of Consecutive Prime Numbers
作成中 Q127 0211 Jogging
作成中 Q128 1327 One-Dimensional Cellular Automaton

■ 探索 (状態遷移)
作成中 Q129 1116 Jigsaw Puzzles for Computers
作成中 Q130 2157 Dial Lock
作成中 Q131 2297 Rectangular Stamps
作成中 Q132 1281 The Morning after Halloween
作成中 Q133 1128 Square Carpets

■ 複合問題
作成中 Q134 1189 Prime Caves
作成中 Q135 0520 Lightest Mobile
作成中 Q136 1301 Malfatti Circles
作成中 Q137 1183 Chain-Confined Path
作成中 Q138 2173 Wind Passages
作成中 Q139 0284 Happy End Problem