貪欲法の証明パターン

• 交換しても損しない

  • 交換しても悪化しない
  • ある順序で選択する貪欲法
  • 順序の遅いものを早いもので置き換えても最大化したいスコアが減少しないことを示す
  • https://penguinshunya.hatenablog.com/entry/2020/01/21/093846

• https://mobile.twitter.com/maspy_stars/status/1198626710599528454

  • 先進性を示す。任意の"時点"で最適な方法であることを、"時系列"順に示す。

  • 最適解に仮定できる性質を課していく（2つ入れ替えても悪くならないのでこの形etc）と、貪欲になることを示す

  • https://maspypy.com/atcoder-参加感想-2020-04-13abc-163

• https://mobile.twitter.com/onakasuita_py/status/1250014171149692930

  • ･各操作において最適たりうる選択(その選択を含む最適解が存在するという意味)を行う

  • ･各操作の後にはより規模の小さい問題に帰着でき、再帰的に解が求まる

  • ･証明は基本的に背理法で、最適解が全て「貪欲による選択」を含まないと仮定して矛盾を示す

    • ex.)区間スケジューリング

    • 時刻0で示す。I=[L,R]をRが最小なものの1つとし、全ての最適解がIを含まないと仮定する。最適解の1つを取り(最適解が存在することは明らか)、そのうちRが最小なものをJ=[L',R']とすると、Jは必ずIと置き換えられることで矛盾。従ってIを採用してよい。

    • こうすると、貪欲の証明でよく目にする「損をしない」というフレーズが出てこない。

• まず下界を示す

  • 下界に一致することを示す
  • よって最適解である
  • ARC111

• 硬貨の問題が貪欲法で解けるための条件 - Qiita

• https://kimiyuki.net/blog/2017/12/03/matroid-greedy-proof/

貪欲法