プログラミングコンテストチャレンジブック
読者サポートページ

正誤情報

正誤情報は、以下の通りです（2013年2月現在）。

P.57 図「DP テーブル」

誤:行見出しと列見出しが逆。
正:以下が正しい図になります

P.66 ソースコード

誤:int dp[MAX_N + 1][MAX_M + 1]; // DPテーブル
正:int dp[MAX_M + 1][MAX_N + 1]; // DPテーブル

P.76 下部

誤：その場所のノードを削除してしまうと、子である１１と１７のノードが
正：その場所のノードを削除してしまうと、子である１０と１７のノードが

P.151 中央およびソースコード

誤：その大きさはたかだか3n×3nとなります。
正：その大きさはたかだか6n×6nとなります。

誤：bool fld[MAX_N * 3][MAX_N * 3];
正：bool fld[MAX_N * 6][MAX_N * 6];

P.156 （例１）

誤：S={10}
正：S={1}

P.220 問題文

誤：k個以上の区間で
正：K個より多くの区間で

P.234 例「入力」

誤: y = {1, -1, 1, 6, 2}
正: y = {1, -1, 0, 0, 1}

P.243 上部

誤：このとき、X^{φ(m)}≡1 (mod m)が成り立ちます。
正：このとき、mと互いに素なxについて、x^{φ(m)}≡1 (mod m)が成り立ちます。

▽ 初版第 6 刷までのもの

P.243 4 行目 (フェルマーの小定理)

誤：
正：

P.81 木の回転

(5 と 6 の場所が逆)

誤： 正：

▽ 初版第 5 刷までのもの

P.64 ソースコード

誤：

// 入力
int n;
int a[MAX_N];

int dp[MAX_N + 1]; // DPテーブル

void solve() {
  dp[0] = 0;
  for (int i = 0; i < n; i++) {
    dp[i + 1] = 1;
    for (int j = 0; j < i; j++) if (a[j] < a[i]) {
      dp[i + 1] = max(dp[i + 1], dp[j] + 1);
    }
  }
  printf("%d\n", dp[n]);
}

正：

// 入力
int n;
int a[MAX_N];

int dp[MAX_N]; // DPテーブル

void solve() {
  int res = 0;
  for (int i = 0; i < n; i++) {
    dp[i] = 1;
    for (int j = 0; j < i; j++) if (a[j] < a[i]) {
      dp[i] = max(dp[i], dp[j] + 1);
    }
    res = max(res, dp[i]);
  }
  printf("%d\n", res);
}

▽ 初版第 4 刷までのもの

P.36 一番下の段落

誤：深さ優先探索では何の対策もしなければ同じ状態を何度も通る可能性がありますが、幅優先探索では同じ状態は一度しか通りません。

誤解を招く表現です。 一般に深さ優先探索と言ったとき、同じ状態を何度も通らないようにすることはアルゴリズムに含まれず、 前のページの Lake Counting のような場合は特殊な場合と言えます。 また、そもそもそのような対策が有効に行いにくい場合も多いです。 (例えば、迷路の例で深さ優先探索を用いた場合、後で同じ場所を訪れたときにそこまでの距離が異なる可能性があります。)
一方、幅優先探索と言ったとき、同じ状態を 1 度しか通らないような処理は大抵アルゴリズムに含まれます。

P.103 例の入力

誤：N=5,N=5,R=8
正：N=5,M=5,R=8

P.156 例1, 例2 の入力

C と N が逆です。

P.180 フィボナッチ数列の一般項

誤：
正：

▽ 初版第 1 刷までのもの

P.57 図「DP テーブル」

i と j が逆です。

P.71 3 行目

誤：その大きい方と（逆転しているなら）交換します。
正：その小さい方と（逆転しているなら）交換します。

連絡先