- 考えたこと
- 与えられたパスをなるべく少ない回数でカットしたい
- あるカットを1つ選んだ時に、それで切れるパスを全部取り除いて、残りについて考える時に、先程のカットは影響しない
- ということは「一番端のパスを含んでなるべく多くのパスを切るカット」をグリーディに選んでいけば良いのでは
- それで良いのか、良いことの証明は？
- 公式解説
- 僕の方法では「aでソートして一番小さいもののb-1を切る」
- 公式解説では「bでソートして一番小さいもののb-1を切る」
- どういう違いがあるか？
- bでソートして一番小さいものがaでも小さい時には差はない
- そうでない時
- なるほど確かに公式の方が正しい
- 区間スケジューリングの貪欲アルゴリズムによく似ている
