from ABC195 ABC195D RE
- 貪欲法の典型的な構築方法選択肢が少ない方から貪欲
- 最も小さい箱が最も入れられる荷物の選択肢が少ない
- 箱が1個の場合を考えると入れられる価値最大のものXを入れるのが最適
- 一般の場合、
- もし最適解にXが含まれないとするとXと交換することで価値が上がるので矛盾
- →よってXは必ず最適解に含まれている。
- Xが最小の箱に入ってない最適解がある場合、最小の箱に入ってる荷物と交換しても最適。
- よって最小の箱にXを入れることにしても最適解が得られることが保証される。
- もし最適解にXが含まれないとするとXと交換することで価値が上がるので矛盾
- 大小比較で条件を満たすもののうちの最大を見つけるのはセグメント木のRange maxで対数オーダーでできるけど、今回の問題制約だったら50×50×50でも大したサイズではないので素朴にやる