drken1215/book_algorithm_solution

拙著「問題解決力を鍛える!アルゴリズムとデータ構造」の補足資料。ソースコードと、章末問題への略解を掲載。

book_algorithm_solution's Issues

5章の章末問題7について

例えば、S="pokemon", T="pachinko"とした時、回答のアルゴリズムを使うと最大共通文字列長が3と出てきますが、目視では1であるように見えます。下記回答で正しいのでしょうか。

https://github.com/drken1215/book_algorithm_solution/blob/master/solutions/chap05.md#57-%E6%9C%80%E9%95%B7%E5%85%B1%E9%80%9A%E9%83%A8%E5%88%86%E5%88%97%E5%95%8F%E9%A1%8C

code13.1のqueueをstackに変更した場合の挙動について

非常に興味深く読ませていただき、社内の勉強会でも利用させていただいてます。
読んでいる中で気になったのですが、

コード13.1中のqueueをstackに変更すれば、深さ優先探索となります

とありますが、厳密にはならないかと思いました。「深さ優先探索」が何を指すかによるのかもしれませんが、少なくともcode13.2と同じ挙動にはならなそうです。

具体的には、図13.3の状況において、「1から3,8に加えて2に辿れる」状況を想定した場合、本来ならば、3から辿れる全て、8から辿れる全て、2から辿れる全てと辿っていくべきかと思いますが、このタイミングで2を辿ることはなさそうです。
seen[2]がtrueになっているからです。

幅優先ならcode13.2で問題ないと思いますが、深さ優先にするならば、22,25行目の処理を17行目付近に移動する必要がありそうです。

この挙動は意図したものでしょうか。

第4刷の誤植

楽しく読ませていただきました。errata.mdに載っていない軽微な誤植や改善点をいくつか見つけたので報告します。

• 319pの最後の行、「頂点番号がiであるような各頂点vに対して、」の後に続くa_iの式の右辺のΣの添え字がiであり、右辺と左辺でiの意味が異なるのがわかりづらい。
• 211pのcode12.4の34行目、「左詰め」→「右詰め」？
• 237pの本文の7行目から8行目にかけて、「どの頂点がどの頂点が子であるか」が誤植
• 296p 図16.12 の説明1行目、「フォート・ファルカーソン法」→「フォード・ファルカーソン法」

トリボナッチの問題4.1の誤り

章末問題 4.6回答例 でメモ参照のインデックスが負数になる可能性がある

章末問題4.6の解答例で、w - a[i - 1]が負数になる可能性があり、その場合次の再起実行時の memoへの参照が負数になります。
そのため、想定外の書き換えや、a[i-1]の値が大きいときにはvectorの領域外への参照により結果が不定となる現象が発生し得ます。

book_algorithm_solution/solutions/chap04.md

Line 201 in bf4af1b

if (func(i - 1, w - a[i - 1], a)) return memo[i][w] = 1;

例えば、以下のような入力は必ずNoになるはずですが、私の実行環境ではYesが出力されることがありました。

20
5
7 9 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55

解決策としては、func()内で w<0 のときfalseで返却してしまうなどが考えられると思います

code_4_8.cpp と 章末問題4.2 のソースコードについて

URL

• https://github.com/drken1215/book_algorithm_solution/blob/master/codes/chap04/code_4_8.cpp

• https://github.com/drken1215/book_algorithm_solution/blob/master/solutions/chap04.md

提案

code_4_8.cppについてですが，
ベースケースの2つについて，メモ化配列の値を更新しないままリターンを行っているため，
memo[0] と memo[1] の中身は -1 のままで，フィボナッチ数列の解が入っていないままだと思います．
従って，ベースケースでも，再帰呼び出しと同様に，メモ化しながら，リターンを行う方が良いのかなと思いました．

同様に，章末問題 4.2 のトリボナッチ数列でも，ベースケースの3つについて，
メモ化配列の値を更新しないまま，リターンを行っていると思います．

ソースコード

long long fibo(int n) {
    // ベースケース
    if (n == 0) {
        return memo[n] = 0;
    } else if (n == 1) {
        return memo[n] = 1;
    }

    // メモをチェック (既に計算済みならば，答えをリターンする)
    if (memo[n] != -1) {
        return memo[n];
    }

    // 答えをメモ化しながら，再帰呼び出し
    return memo[n] = fibo(n - 1) + fibo(n - 2);
}

long long tribonacci(int n) {
    using namespace std;

    // ベースケース
    if (n == 0) {
        return memo[n] = 0;
    } else if (n == 1) {
        return memo[n] = 0;
    } else if (n == 2) {
        return memo[n] = 1;
    }

    // メモをチェック (既に計算済みならば，答えをリターンする)
    if (memo[n] != -1) {
        return memo[n];
    }

    // 答えをメモしながら，再帰呼び出し
    return memo[n] = tribonacci(n - 1) + tribonacci(n - 2) + tribonacci(n - 3);
}

P280: 全域木間での辺の交換に関する説明

素晴らしい本をご執筆いただきありがとうございます。大変勉強になりました。

この度、本書のp280の全域木間での辺の交換 の項目の最後の行について誤記(?)があるように思い、issueを投稿させていただきます。
このとき、Tに含まれるがSには含まれない辺fが存在して、S'=S-e+fも全域木となります。
とありますが、この文は正しくは
このとき、Tに含まれるがSには含まれない辺であり、かつS'=S-e+fも全域木Tとなるような辺fが存在します。
ではないでしょうか?
Tに含まれるがSには含まれない辺全てについて、S'=S-e+fも全域木となるが成り立つわけではないと思いました。
S'=S-e+fも全域木となるが成立するには、辺fがTに含まれるがSには含まれない辺で、かつ辺fがS, eに関する基本カットであるという条件が必要だからです。
お忙しい中恐縮ですがご確認いただければ幸いです。何卒宜しくお願い致します。

章末問題の解答について

5章以降の章末問題の解答はsolutionの中には無いようですが、まだ公開されていないのでしょうか？
それともどこか他のところにありますでしょうか？

第2章の章末問題の誤植について

最近AtCoderを始めた者で、アルゴリズムの勉強として楽しく読ませていただいています。
私の持っている第6刷ではP28 章末問題2.3 4行目に"n % p == 0"とあるのですが、"N % p == 0"の誤植でしょうか？
errata.mdに載っていなかったので、報告させていただきました。

章末問題 7.2 の計算量について

章末問題 7.2 は AtCoder Regular Contest 092 - C - 2D Plane 2N Points を元とした問題となります。

こちら、著書の中では

O(N log N) で求めるアルゴリズムを設計してください

との指示があります。一方、本リポジトリに含まれている解説では以下のように書かれていますが、こちらのリンク先の説明および実装では O(N^2) の回答が紹介されております。

7.2 (ARC 092 C - 2D Plane 2N Points)

問題 7.1 では一次元直線上の点同士のペアを組んでいく問題でしたが、今回は二次元平面上の点同士のペアを組んでいく問題です。難易度はだいぶ上がりますが、丁寧に考察することで解くことができます。具体的なアルゴリズムについては、次の記事に記しています。

AtCoder ARC 092 C - 2D Plane 2N Point

（おそらく、判定を行っている内側のループで線形探索をしている部分について、既に選んだものを除外しつつ2分探索するといった形に書き換えができれば O (N log N) への削減もできるとは思うのですが・・・少し考えてみたものの思いつかず・・・）