プログラミングコンテストチャレンジブック 第2章 その3

ずいぶん久しぶりになってしまいました。第2章後半「貪欲法」の残りを読みます。

  • 貪欲法
    • Fence Repair
      • 板を切る時に切る前の長さのぶんコストがかかるという条件で求める長さの板に分割する最小コストを計算する問題
      • 二分木を使って再帰的に解く(Haskell を使いたくなりますね)
      • このアルゴリズムはハフマン符号をつくる方法と同じらしい
      • 最適な(最小コストの)時に最も短い板2つが最後に切り出されるというのをさらっと書いてますがそんなに自明でもないような……。もうちょっと説明が欲しいですね

どうも本書は(少なくとも初級編は)考え方を説明するというよりは、よく使うアルゴリズムをとにかくたくさん紹介していくという方針のようなのでがんがんスピードアップして読んでいこうと思います。まだまだ先も長いですし。