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

今日は第2章後半「貪欲法」について。

• 貪欲法
  • 硬貨の問題 - 金額の大きい硬貨から使っていく
  • 区間スケジューリング問題 - より早い時間に終わる区間を選んでいく
  • Best Cow Line - これは「ゲーデル/エッシャー/バッハ」のMUゲームを彷彿とさせますね
    • 辞書順を扱う問題では貪欲法が有効なことが多い
  • Saruman's Army - Saruman って Load of the Rings のサルマンでしょうか？

ここでもそんなに特筆することはありませんでした。