AOJサイト | 正誤情報

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

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

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

• ALDS1_:Part2 2～13章,18,19章
• DSL_:Part 3 14章
• GRL_:Part 3 15章
• CGL_:Part 3 16章
• DPL_:Part 3 17章
• NTL_:Part 3 18.3

補足:
*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 その他の問題

• DSL_2_A: Range Minimum Query
• DSL_2_B: Range Sum Query

363p 15.6 その他の問題

• GRL_1_B: Single Source Shortest Path (Negative Edges)
• GRL_3_B: Bridge
• GRL_3_C: Strongly Connected Components
• GRL_2_B: Minimum-Cost Arborescence
• GRL_6_A: Maximum Flow
• GRL_7_A: Bipartite Matching

410p 16.14 その他の問題

• CGL_5_A: Closest Pair
• CGL_4_B: Diameter of a Convex Polygon
• CGL_4_C: Convex Cut

433p 17.6 その他の問題

• DPL_1_C: Knapsack Problem
• DPL_1_E: Edit Distance (Levenshtein Distance)
• DPL_2_A: Traveling Salesman Problem
• DPL_2_B: Chinese Postman Problem

448p 18.4 その他の問題

• NTL_1_A: Prime Factorize
• NTL_1_C: Least Common Multiple
• NTL_1_D: Euler's Phi Function
• NTL_1_E: Extended Euclid Algorithm

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 計算幾何学、動的計画法★★★★☆

正誤情報

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

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
			

for ( int j = N - 1; j >= i; j-- ) {

for ( int j = N - 1; j >= i + 1; j-- ) {

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)
			

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

• 公開日：2015/01/22
• 更新日：2015/01/29 問題へのリンク追加
• 更新日：2019/07/17 正誤更新

　発行：株式会社 マイナビ出版

書籍紹介サイトに戻る