「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」サポートサイト

本サイトでは、書籍のサポート情報を掲載していきます。

AOJ - オンライン プログラミング チャレンジ サイト

本書でとりあげた問題をオンラインジャッジできるAIZU ONLINE JUDGEのサイトです。

解説問題

「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」オンラインジャッジ一覧
問題ページ本文記事補足
ALDS1_1_D: Maximum Profit046p2.4 導入問題
ALDS1_1_A: Insertion Sort054p3.2 挿入ソート
ALDS1_2_A: Bubble Sort060p3.3 バブルソート
ALDS1_2_B: Selection Sort065p3.4 選択ソート
ALDS1_2_C: Stable Sort070p3.5 安定なソート
ALDS1_2_D: Shell Sort074p3.6 シェルソート
ALDS1_3_A: Stack082p4.2 スタック
ALDS1_3_B: Queue086p4.3 キュー
ALDS1_3_C: Doubly Linked List094p4.4 連結リスト
ALDS1_3_D: Areas on the Cross-Section Diagram114p4.6 データ構造の応用:面積計算
ALDS1_4_A: Linear Search119p5.2 線形探索
ALDS1_4_B: Binary Search122p5.3 二分探索
ALDS1_4_C: Dictionary126p5.4 ハッシュ
ALDS1_4_D: Allocation136p5.6 探索の応用:最適解の計算
ALDS1_5_A: Exhaustive Search142p6.2 全探索
ALDS1_5_C: Koch Curve146p6.3 コッホ曲線
ALDS1_5_B: Merge Sort152p7.1 マージソート
ALDS1_6_B: Partition158p7.2 パーティション
ALDS1_6_C: Quick Sort163p7.3 クイックソート
ALDS1_6_A: Counting Sort168p7.4 計数ソート
ALDS1_5_D: The Number of Inversions175p7.6 反転数
ALDS1_6_D: Minimum Cost Sort179p7.7 最小コストソート
ALDS1_7_A: Rooted Trees188p8.2 根付き木の表現
ALDS1_7_B: Binary Tree193p8.3 二分木の表現
ALDS1_7_C: Tree Walk198p8.4 木の巡回
ALDS1_7_D: Reconstruction of the Tree203p8.5 木巡回の応用:木の復元
ALDS1_8_A: Binary Search Tree I209p9.2 二分探索木:挿入
ALDS1_8_B: Binary Search Tree II214p9.3 二分探索木:探索
ALDS1_8_C: Binary Search Tree III217p9.4 二分探索木:削除
ALDS1_9_A: Complete Binary Tree234p10.2 完全二分木
ALDS1_9_B: Maximum Heap236p10.3 最大・最小ヒープ
ALDS1_9_C: Priority Queue240p10.4 優先度付きキュー
ALDS1_10_A: Fibonacci Number249p11.2 フィボナッチ数列
ALDS1_10_C: Longest Common Subsequence253p11.3 最長共通部分列
ALDS1_10_B: Matrix Chain Multiplication257p11.4 連鎖行列積
ALDS1_11_A: Graph269p12.2 グラフの表現
ALDS1_11_B: Depth First Search273p12.3 深さ優先探索
ALDS1_11_C: Breadth First Search282p12.4 幅優先探索
ALDS1_11_D: Connected Components287p12.5 連結成分
ALDS1_12_A: Minimum Spanning Tree296p13.2 最小全域木
ALDS1_12_B: Single Source Shortest Path I302p13.3 単一始点最短経路
ALDS1_12_C: Single Source Shortest Path II309p単一始点最短経路 II
DSL_1_A: Disjoint Set: Union Find Tree318p14.1 互いに素な集合*1
DSL_2_C: Range Search (kD Tree)324p14.2 領域探索
GRL_1_C: All Pairs Shortest Path336p15.1 全点対間最短経路
GRL_4_B: Topological Sort342p15.2 トポロジカルソート
GRL_3_A: Articulation Point348p15.3 関節点
GRL_5_A: Diameter of a Tree353p15.4 木の直径
GRL_2_A: Minimum Spanning Tree358p15.5 最小全域木
CGL_2_A: Parallel/Orthogonal374p16.2 直線の直交・平行判定*2
CGL_1_A: Projection376p16.3 射影*2
CGL_1_B: Reflection378p16.4 反射*2
CGL_2_D: Distance380p16.5 距離*2
CGL_1_C: Counter-Clockwise384p16.6 反時計回り*2
CGL_2_B: Intersection387p16.7 線分の交差判定*2
CGL_2_C: Cross Point390p16.8 線分の交点*2
CGL_7_D: Cross Points of a Circle and a Line393p16.9 円と直線の交点
CGL_7_E: Cross Points of Circles396p16.10 円と円の交点
CGL_3_C: Polygon-Point Containment398p16.11 点の内包
CGL_4_A: Convex Hull401p16.12 凸包*3
CGL_6_A: Segment Intersections: Manhattan Geometry405p16.13 線分交差問題*4
DPL_1_A: Coin Changing Problem412p17.1 コイン問題
DPL_1_B: 0-1 Knapsack Problem416p17.2 ナップザック問題
DPL_1_D: Longest Increasing Subsequence421p17.3 最長増加部分列
DPL_3_A: Largest Square425p17.4 最大正方形
DPL_3_B: Largest Rectangle428p17.5 最大長方形
ALDS_1_C: Prime Numbers436p18.1 素数判定
ALDS1_1_B: Greatest Common Divisor441p18.2 最大公約数
NTL_1_B: Power445p18.3 べき乗
ALDS1_13_A: 8 Queens Problem450p19.1 8クイーン問題
ALDS1_13_B: 8 Puzzle455p19.2 8パズル
ALDS1_13_C: 15 Puzzle461p19.3 15パズル

補足:
*1 (322pの考察に補足)この実装では、経路圧縮における rank の更新は行いません。実際、ノード x の高さは rank[x] 以下となります。
*2 「入力はすべて整数で与えられます。」
*3 凸包の辺上の点も含める場合は404ページ、14,22行目の != CLOCKWISE を == COUNTER_CLOCKWISE に置き換えます。
*4 制約の補足:-1,000,000,000 ≦ x1, y1, x2, y2 ≦ 1,000,000,00

その他の問題

(書籍にはカンタンなヒントが掲載されています)

334p 14.3 その他の問題

363p 15.6 その他の問題

410p 16.14 その他の問題

433p 17.6 その他の問題

448p 18.4 その他の問題

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

(★☆は5段階評価の難易度で★は1、☆は0.5です。書籍ではリンクのみ)

■ 整列・探索

  1. 1187 ICPC Ranking 整列★
  2. 2104 Country Road 整列★☆
  3. 0529 Darts 二分探索★★
  4. 0539 Pizza 二分探索★★

■ データ構造

  1. 1173 The Balance of the World スタック★
  2. 0558 Cheese キュー★★
  3. 0301 Baton Relay Game リスト★★☆
  4. 0282 Programming Contest 優先度付きキュー★★★
  5. 2170 Marked Ancestor Union-Find ★★★☆
  6. 1330 Never Wait for Weights Union-Find ★★★☆

■ 再帰・分割統治

  1. 0507 Square 再帰★★☆
  2. 0525 Osenbei 全探索 ★★☆
  3. 2057 The Closest Circle 分割統治★★★★

■ グラフ

  1. 0508 String With Rings 深さ優先探索★★
  2. 1166 Amazing Mazes 幅優先探索★★
  3. 2511 Sinking island 最小全域木★★★
  4. 0519 Worst Sportswriter トポロジカルソート★★☆
  5. 0526 Boat Travel 単一始点最短経路★★☆
  6. 1182 Railway Connection 全点対間最短経路★★★
  7. 1162 Discrete Speed 単一始点最短経路★★★☆
  8. 1196 Bridge Removal 木の直径★★★☆
  9. 2224 Save your cat 最小全域木★★★☆

■ 動的計画法

  1. 2272 Cicada 2次元動的計画法★☆
  2. 1167 Pollock's conjecture コイン問題★★
  3. 2090 Repeated Subsequences 最長共通部分列★★☆
  4. 0561 Books ナップザック問題★★☆
  5. 2431 House Moving 最長増加部分列★★★
  6. 0310 Frame 2次元動的計画法★★★☆

■ 計算幾何学

  1. 1053 Accelerated Railgan 反時計回り★★☆
  2. 2003 Railroad Conflict 交差判定・交点★★☆
  3. 1157 Roll-A-Big-Ball 距離★★★
  4. 1298 Separate points 凸包★★★
  5. 1047 Crop Circle 円と円の交点★★★☆
  6. 1247 Monster Trap 多角形の点の包含★★★★☆

■ 整数

  1. 1257 Sum of Consecutive Prime Numbers 素数判定★★
  2. 0211 Jogging 最大公約数★★☆
  3. 1327 One-Dimensional Cellular Automaton 繰り返し自乗法★★★

■ 探索(状態遷移)

  1. 1116 Jigsaw Puzzles for Computers バックトラック★★☆
  2. 2157 Dial Lock DFS ★★★
  3. 2297 Rectangular Stamps BFS ★★★
  4. 1281 The Morning after Halloween A* ★★★☆
  5. 1128 Square Carpets IDA* ★★★★☆

■ 複合問題

  1. 1189 Prime Caves 整数論、動的計画法★★★
  2. 0520 Lightest Mobile 整数論、木★★★
  3. 1301 Malfatti Circles 探索、計算幾何学★★★
  4. 1183 Chain-Confined Path 計算幾何学、グラフ★★★★
  5. 2173 Wind Passages 計算幾何学、グラフ★★★★
  6. 0284 Happy End Problem 計算幾何学、動的計画法★★★★☆

正誤情報

見つかり次第報告していきます

「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」正誤表
ページ箇所 備考
16下から4行目 最強最速アルゴリズマー養成講座 最強最速アルゴリズマー養成講座 1~5刷
70コード3行目 for j = N-1 downto i for j = N-1 downto i+1 1,2刷
71Program 3.2
1 isStable(in, out)
2   for i = 1 to N-1
3     for j = i+1 to N
4       for a = 1 to N-1
5         for b = a+1 to N
6           if in[i] と out[j] の数字が等しい
               && in[i] == out[b] && in[j] == out[a]
7             return false
8 return true
			
1 isStable(in, out)
2   for i = 0 to N-1
3     for j = i+1 to N-1
4       for a = 0 to N-1
5         for b = a+1 to N-1
6           if in[i] と in[j] の数字が等しい
               && in[i] == out[b] && in[j] == out[a]
7             return false
8 return true
			
1刷
72解凍例 コード8行目
for ( int j = N - 1; j >= i; j-- ) {
for ( int j = N - 1; j >= i + 1; j-- ) {
1,2刷
92擬似コード 18行目 } }は不要 1刷
116解答例 27,34行目 int t = 0;、t += ans[i]; 不要な記述につき削除 1,2刷
172解答例 23行目 C[i] = C[i] + C[i + 1]; C[i] = C[i] + C[i - 1]; 1刷
2245行目 時間と場所に異存します。 時間と場所に依存します。 1刷
22531行目 print(S); // 3: 1 2 4 8 print(S); // 4: 1 2 4 8 1,2刷
250Program 11.2 4行目 return fibonacci(i - 2) + fibonacci(i - 1) return fibonacci(n - 2) + fibonacci(n - 1) 1,2刷
251Program 11.3 6行目 return fibonacci(i - 2) + fibonacci(i - 1) return fibonacci(n - 2) + fibonacci(n - 1) 1,2刷
235解答例 7行目 return 2 * i + 1 return 2 * i + 1; 1刷
262解答例 20行目 m[i][j] = min(m[i][j], m[i][k] + m[i][k] + m[k + 1][j] + … m[i][j] = min(m[i][j], m[i][k] + m[k + 1][j] + … 1刷
336問題文 1行目 重み付き無向グラフ 重み付き有向グラフ 1,2刷
336問題文 入力 下より2行目 i番目の辺が結ぶ(無向 i番目の辺が結ぶ(有向 1,2刷
381Program 16.18
タイトル
直線 s と点 p の距離 直線 l と点 p の距離 1刷
409Program 16.28
平面走査の解答例
55,56行目
55 set<int>::iteretor b = lower_bound(
  BT.begin(), BT.end(), S[EP[i].seg].p1.x);// O(log n) 56 set<int>::iterator e = upper_bound(
  BT.begin(), BT.end(), S[EP[i].seg].p2.x);// O(log n)
55 set<int>::iteretor b = BT.lower_bound(
  S[EP[i].seg].p1.x); // O(log n) 56 set<int>::iterator e = BT.upper_bound(
  S[EP[i].seg].p2.x); // O(log n)
1,2刷補足1:
427解答例 8-14行目
for ( int i = 0; i < H; i++ ) {
  for ( int j = 0; j < W; j++ ) {
    dp[i][j] = (G[i][j] + 1) % 2;
  }
}

int maxWidth = 0;
			
int maxWidth = 0;
for ( int i = 0; i < H; i++ ) {
  for ( int j = 0; j < W; j++ ) {
    dp[i][j] = (G[i][j] + 1) % 2;
    maxWidth |= dp[i][j];
  }
}
			
1刷 補足2:
446Program 18.7 1行目 pos(x, n) pow(x, n) 1~3刷

補足1: "誤"のコードでは、 O(N) で動作してしまうため、std::set が持つ関数を利用します。
補足2: "誤"のコードでは、HまたはWが1の入力に対して不正解となる可能性があります。
スタックオーバーフローを回避するために、配列dpとGは大域変数として宣言するか、動的にメモリを確保してください。