現時点で判明している誤植などを掲載していきます。
| 該当ページ | 該当箇所 | 誤 | 正 | 備考 | 対応 |
|---|---|---|---|---|---|
| p. 22 | 表 2.2 の 1 行目 | 2, 12, 25, 130, 30, 120 | 2, 12, 25, 125, 32, 120 | 4 刷で対応 | |
| P. 22 | 表 2.2 のマス (N = 25, 2^N) | - | 33,554,432 | 4 刷で対応 | |
| p. 41 | 問題 3.7 | O(2^N) | O(N2^N) | 4 章の再帰関数を用いれば O(2^N) も可能ですが、ビット演算を用いる方法では O(N2^N) となります | 4 刷で対応 |
| p. 54 | 図 4.5 の根元からの分岐の右側 | a3 を選ばない | a3 を選ぶ | 3 刷で対応 | |
| p. 90 | 問題 5.9 の出典 | AtCoder Educational Contest | AtCoder Educational DP Contest | 3 刷で対応 | |
| p. 101 | 6.6 節の問題文 | 整数 K 以上の範囲内での最小値を求めてください． | 整数 K 以上の範囲内での最小値を求めてください．ただし，ai + bj >= K を満たすような (i, j) の組が少なくとも 1 つ以上存在するものとします． | p. 34 も同様 | 3 刷で対応 |
| p. 102 | code 6.4 | codes フォルダ以下 chap06/code_6_4.cpp のように変更 | 元のコードでは 27 行目の int val = *iter; において、iter = b.end() である可能性があり、エラーが起こり得ました |
3 刷で対応 | |
| p. 106 | 6.8 節の「判定問題」 | (N - 1) / 2 個あるかどうか | (N - 1) / 2 個以上あるかどうか | 7 刷で対応 | |
| p. 108 | 問題 6.7 | 区間に属する値の総和をとります． | 区間に属する値のメディアンをとります． | 4 刷で対応 | |
| p. 109 | コイン問題 | 500 円玉，100 円玉，50 円玉，5 円玉，1 円玉 | 500 円玉，100 円玉，50 円玉，10 円玉，5 円玉，1 円玉 | 10 円玉が抜けていました | 6 刷で対応 |
| p. 158 | 10.1.3 節 | sub-grpah | sub-graph | スペルミス | 6 刷で対応 |
| p. 165 | code 10.2 の 1 行目 | 8 13 | 8 12 | 4 刷で対応 | |
| p. 189 | 11.7 節 | O(|E|α(|V|)) | O(|V| + |E|α(|V|)) | 辺がまったくないなど、|V| >> |E| である可能性もありました | 6 刷で対応 |
| p. 211 | code 12.4 の 34 行目のコメント | ヒープの最大値を左詰め | ヒープの最大値を右詰め | 7 刷で対応 | |
| p. 213 | code 12.5 | codes フォルダ以下 chap12/code_12_5.cpp のように変更 | 22 行目に sum[0] = num[0]; を追加しました。元のコードでは 0 を含む配列を正確にソートできない状態となっていました。 |
6 刷で対応 | |
| p. 215 | 問題 12.3 | N, k を正の整数とします (k <= N)． | N, K を正の整数とします (K <= N)． | 4 刷で対応 | |
| p. 215 | 問題 12.6 の出典 | AtCodet Tenka1 Programming Contest | AtCoder Tenka1 Programmer Contest | 4 刷で対応 | |
| p. 226 | code 13.3 | codes フォルダ以下 chap13/code_13_3.cpp のように変更 | 頂点 s を始点とした BFS を意図していたはずが、頂点 0 を始点とした BFS となっていました | 5 刷で対応 | |
| p. 237 | 入力形式 (13.10 節) | 木の辺数は N-1 ですので、0-indexed の場合には、最後の添字は N-2 になります | 6 刷で対応 | ||
| p. 240 | code 13.9 の 21 行目のコメント | 部分き | 部分木 | 4 刷で対応 | |
| p. 251 | 入力形式 (14.5.2 節) | 添字のミス | 5 刷で対応 | ||
| p. 254 | 図 14.8 | 路を道にしても長さは減少しない | 路を道にしても長さは増加しない | 6 刷で対応 | |
| p. 269 | 問題 14.1 の出典 | AtCoder Typical DP Contest | AtCoder Educational DP Contest | 5 刷で対応 | |
| p. 281 | 15.5 節のクラスカル法の正当性の証明 | w(f) >= w(e) | w(f) <= w(e) | 5 刷で対応 | |
| p. 287 | 16.2.3 節 | 2 頂点 s, t \in S | 2 頂点 s, t \in V | 6 刷で対応 | |
| p. 289 | 図 16.6 の右下のグラフ | 辺 (4, 6), (6, 8), (8, t), (7, 9), (9, t) | いずれも向きが逆 | 5 刷で対応 | |
| p. 296 | 図 16.12 のキャプション | フォート・ファルカーソン法 | フォード・ファルカーソン法 | 7 刷で対応 | |
| p. 298 | 入力形式 (16.4 節) | 添字のミス | 5 刷で対応 | ||
| p. 298 | 16.4 節 | s = 0, t = 1 | s = 0, t = N-1 | code 16.1 との整合性が取れていませんでした | 6 刷で対応 |
| p. 311 | 多項式時間帰着の注 a | X を解く多項式時間アルゴリズム P(X) | X を解くアルゴリズム P(X) | オラクルとして使用する P(X) については、多項式時間である必要はありませんでした | 4 刷で対応 |
| p. 319 | 17.5.2 節 | 6 刷で対応 |
その他の改良点です。
| 該当ページ | 該当箇所 | 修正前 | 修正後 | 備考 | 対応 |
|---|---|---|---|---|---|
| p. 64 | 5.2 節の本文 | dp[3] = 3 となります | dp[3] = 3 となります． | 句点が抜けていました | 4 刷で対応 |
| p. 68 | 注 4 | if (i >1) |
if (i > 1) |
半角スペースが抜けていました | 3 刷で対応 |
| p. 91 | 6.1 節の本文 | 二分探索法の解説します． | 二分探索法を解説します． | 3 刷で対応 | |
| p. 104 | code 6.5 | codes フォルダ以下 chap06/code_6_5.cpp のように変更 | 元のコードは変数 right の初期値が INF であったため、その計算量は本文中に記載のものと整合していませんでした。 |
7 刷で対応 | |
| p. 121 | 問題 7.2 | 最大で何個の仲良しペアを作ることができるかをO(N log N) で求めるアルゴリズムを設計してください． | いま，仲良しであるような赤い点と青い点をペアにしていくことを考えます．1 つの点が複数のペアに属することはできないものとします．最大で何組のペアを作ることができるかを O(N log N) で求めるアルゴリズムを設計してください． | 題意がとりづらかったので改めました | 3 刷で対応 |
| p. 121 | 問題 7.2 | O(N log N) | O(N^2) | O(N log N) でも実現できますが、不必要に難易度が高いので O(N^2) としました | 5 刷で対応 |
| p. 237 | 13.10 節の 7〜8 行目 | どの頂点がどの頂点が子であるか | どの頂点がどの頂点の子であるか | ||
| p. 243 | 14.1.2 節 | 赤太辺 | 赤辺 | 図 14.1 の赤辺が太いとは言えないため | 6 刷で対応 |
| p. 299 | code 16.1 | vector<int> seen; |
vector<bool> seen; |
bool 型にした方が意味が通りやすい | 6 刷で対応 |
| p. 311 | 17.1 節 | - | 多項式時間帰着の定義の仕方には，いくつかの流儀があります．ここでの定義はチューリング帰着とよばれるものです．他に，計算量理論において主流の定義として，多対一多項式時間帰着があります． | 脚注を追加 | 4 刷で対応 |
| p. 314 | 17.2 節の注 2 | non-deterministic の意味の詳細については本書では省略しますが，関心のある方はブックガイド [15], [16] に挙げた書籍などでチューリング機械について調べてみてください． | トル | チューリング機械について調べることへの誘導が，本文と被るため | 4 刷で対応 |
| p. 316 | 17.4 節 | 本書では，チューリング帰着とよばれる多項式時間帰着の考え方を用いて NP 完全を定義しています．他に計算量理論で主流の定義として，多対一多項式時間帰着を用いたものもあります．両者の定義が等価かどうかは未解決問題です．関心のある方は，ブックガイド [15], [16], [20] などを読んでみてください． | 脚注を追加 | 4 刷で対応 | |
| p.319 | 17.5.2 節 | a_i = 4^|E| + Σ_{i ∈ I(v)} 4^i | a_i = 4^|E|+ Σ_{t ∈ I(v)} 4^t | a の添字 i は頂点番号を表していて、Σ の添字 i とは意味が異なっています。紛らわしいため、Σ の添字を t としました | 7 刷で対応 |
| p. 321 | NP 困難の定義 | X はクラス NP 困難 (class NP-hard) に属するといいます．また，NP 困難に属する問題を，NP 困難問題といいます． | X は NP 困難問題であるといいます． | NP 困難をクラスとよぶことは一般的でないため | 4 刷で対応 |
| p. 321 | NP 困難の定義の下の文章 | つまり NP 困難とは，判定問題に限定せず，NP 完全問題と同等かそれ以上に難しい問題のクラスのことです． | つまり NP 困難問題とは，判定問題に限定せず，NP 完全問題と同等かそれ以上に難しい問題のことです． | 同上 | 4 刷で対応 |
| p. 338 | 問題 18.3 | 出典を表すカッコの閉じカッコが橙色 | 出典を表すカッコの閉じカッコが黒色 | 6 刷で対応 |