2017.12.26

【正誤情報】『最強最速アルゴリズマー養成講座』

最強最速アルゴリズマー養成講座

■本書第1刷の内容に下記のような誤りがありました。お詫びの上、訂正いたします。

●p.63 本文上から6行目
(誤) 友人それぞれが共通の興味のある話題
(正) 友人全員が興味のある共通の話題

●p.67 「問題の解説」の上から2行目
(誤) 最小値を返す
(正) 最大値を返す

●p70 「5-2 C#」 022行目
(誤) if(ans < dic[key]) ans = dic[key];
(正) ans = Math.Max(ans, dic[key]);

●p71 「5-2 C++」 004行目に挿入追加
 #include<algorithm>

●p71 「5-2 C++」 026行目
(誤) if(ans < it->second) ans = it->second;
(正) → ans = max(ans, it->second);

●p72 「5-2 Java」 021行目
(誤) if( ans < dic.get(key) ) ans = dic.get(key);
(正) ans = Math.max(ans dic.get(key));

●p78 「5-4 C#」のソースコードを以下に変更
using System;
using System.Collections.Generic;

public class Cryptography {
 public long encrypt(int[] numbers)
 {
  long ret = 1;
  Array.Sort(numbers);
  numbers[0]++;
  for (int i = 0; i < numbers.Length; i++)
  {
   ret *= numbers[i];
  }
  return ret;
 }
}

●p78 「5-4 C++」のソースコードを以下に変更
#include<vector>
#include<algorithm>
using namespace std;

class Cryptography {
public:
 long long encrypt(vector<int> numbers)
 {
  long long ret = 1;
  sort(numbers.begin(), numbers.end());
  numbers[0]++;
  for (int i = 0; i < numbers.size(); i++)
  {
   ret *= numbers[i];
  }
  return ret;
 }
};

●p79 「5-4 Java」のソースコードを以下に変更
import java.util.*;

public class Cryptography {
 public long encrypt(int[] numbers)
 {
  long ret = 1;
  Arrays.sort(numbers);
  numbers[0]++;
  for (int i = 0; i < numbers.length; i++)
  {
   ret *= numbers[i];
  }
  return ret;
 }
}

●p81 「Definition:クラスと関数の定義」のC#の項目
(誤)public int[] digits(int bas)
(正)public int[] digits(int base)

●p81 「Constraints:パラメータ範囲」の項目
(誤) 3~30の要素をもつ配列
(正) 3~30の整数

●p83 「Table5-2 10進数の3進数への変換」の「9」と「10」の項目を以下に
10進表記  変形式          3進表記  各桁の和
9     1×3^2 + 0x3^1 + 0x3^0   100    1

10 1×3^2 + 0x3^1 + 1×3^0 101 2

●p90 本文上から3行目
(誤) 0か数文字を追加します。
(正) 数文字を追加します(ただし、文字を追加しなくてもかまいません)。

●p102 本文下から7行目
(誤) ・1人ずつ選び、その人が友人かどうか調べる。
(正) ・友人jを選び、その人が友人かどうかを調べる。

●p103 「5-8 C#」のソースコードで以下をすべて置換
 i1 → i
 i2 → j
 i3 → k

●p103 「5-8 C++」のソースコードで以下をすべて置換
 i1 → i
 i2 → j
 i3 → k

●p104 「5-8 Java」のソースコードで以下をすべて置換
 i1 → i
 i2 → j
 i3 → k

●p118 1行目の見出し
(誤)deque(デキュー)
(正)deque(デック)

●p120 「Fig5-44 フィボナッチ数列のグラフ」の図の「fib(2)」の上の数字
(誤)3
(正)2

●p136 本文下から4行目からの「増えませんし、計算量も~」を以下に変更
増えません。現在はあまり計算時間を気にする必要はありませんが、第6章で出てくる計算量の概念を用いると、

●p181 「7-6 C++」のソースコード 011行目
(誤) Math.Max
(正) max

●p181 「7-6 Java」のソースコード 011行目
(誤) Math.Max
(正) Math.max

●p184 「7-7 C#」のソースコードで以下をすべて置換
 ps[j] → ps[i]

●p184 「7-7 C++」のソースコードで以下をすべて置換
 ps[j] → ps[i]

●p184 「7-7 Java」のソースコードで以下をすべて置換
 ps[j] → ps[i]

●p216 「Fig7-38」のC3の項目の「a 基準の握手」の図の線の修正
(誤) b、c、e、fから線が出ている
(正) b、d、fから線を出す

●p217 「Fig7-38」のC5の項目の「a 基準の握手」の図の線の修正
(誤) b、e、g、i、lから線が出ている
(正) b、d、f、j、k、lから線を出す

●p218 本文上から1行目
(誤) この計算方法を
(正) この問題で出てくる数を

●p291 ページ上の節見出し部分
(誤) Div2
(正) Div1

●p322 「9-8 C++」のソースコード 010行目
(誤) int[][] board = new int[1005][10005];
(正) vector<vector<int> > board(1005, vector<int>(1005));

●p327 ページ上の節見出し部分
(誤) Div2 Level 2/Div 2 Level 3
(正) Div1 Level 2/Div 2 Level 3

●p327 本文上から4行目
(誤) 整数
(正) 正数

●p332 「9-10 C#」のソースコード 027行目のコメントを以下に
(誤) //誤差の判定が甘いので、lowでもhighでもかまわない
(正) //lowとhighとの差が十分に小さくなるので、lowでもhighでもかまわない

●p332 「9-10 C++」のソースコード 002行目に挿入追加
 #include<vector>

●p333 「9-10 C++」のソースコード 015行目を以下に
(誤) long count = 0;
(正) long long count = 0;

●p333 「9-10 C++」のソースコード 017行目を以下に
(誤) long cut = 0;
(正) long long cut = 0;

●p333 「9-10 C++」のソースコード 020行目を以下に
(誤) long next = (long)(sticks[j] / mid;
(正) long long next = (long)(sticks[j] / mid;

●p333 「9-10 C++」のソースコード 029行目のコメントを以下に
(誤) //誤差の判定が甘いので、lowでもhighでもかまわない
(正) //lowとhighとの差が十分に小さくなるので、lowでもhighでもかまわない

●p333 「9-10 Java」のソースコード 023行目のコメントを以下に
(誤) //誤差の判定が甘いので、lowでもhighでもかまわない
(正) //lowとhighとの差が十分に小さくなるので、lowでもhighでもかまわない

●p341 「9-12 C++」のソースコードを以下に変更
#include<algorithm>
using namespace std;

class InfiniteSequence2 {
public:
 long long dp[9999999];
 long long calc(long long n, int p, int q, int x, int y){
  int i;
  dp[0] = 1;
  for(i = 1; i <= n; i++){
   dp[i] = 0;
   long long nexta = i / p – x;
   long long nextb = i / q – y;
   if(nexta <= 0) dp[i]++; else dp[i] += dp[nexta];
   if(nextb <= 0) dp[i]++; else dp[i] += dp[nextb];
  }
  return dp[n];
 }
};

●p347 「9-16 C#」のソースコードを以下に変更
using System;

public class InfiniteSequence2 {
 const int MAX = 1000000;
 long[] dp = new long[MAX];
 public long calc(long n, int p, int q, int x, int y)
 {
  if (n <= 0) return 1;
  if (n < MAX)
  {
   if (dp[n] != 0) return dp[n];
   return dp[n] = calc(n / p – x, p, q, x, y) + calc(n / q – y, p, q, x, y);
  }
  return calc(n / p – x, p, q, x, y) + calc(n / q – y, p, q, x, y);
 }
}

●p356 「9-17 C#」のソースコードの019行目のコメントを変更
(誤) //縦の棒を入れる場合
(正) //横の棒を入れる場合

●p357 「9-17 C++」のソースコードの022行目のコメントを変更
(誤) //縦の棒を入れる場合
(正) //横の棒を入れる場合

●p358 「9-17 Java」のソースコードの015行目のコメントを変更
(誤) //縦の棒を入れる場合
(正) //横の棒を入れる場合

●p384 「10-4 C#」のソースコードの023行目
(誤) !check[now]
(正) !check[j]

●p385 「10-4 C++」のソースコードの024行目
(誤) !check[now]
(正) !check[j]

●p386 「10-4 Java」のソースコードの024行目
(誤) !check[now]
(正) !check[j]

●p389、p390 「Fig10-15」と「Fig10-16」の図を入れ替え

●p408 「ソースコード」の上の本文下から5行目の数式を以下に変更
 a × a <= a × (p/a) = p

●p408 「ソースコード」の上の本文下から3行目の数式を以下に変更
 a<=√p

●p408 「ソースコード」の上の本文下から2行目
(誤) a<=√a
(正) a<=√p