from 競技プログラミングで解法を思いつくための典型的な考え方
- ペナルティの最大値を最小化したい
- 最大値の最小化
- ペナルティが時間と共に増えるのが厄介
- しかもペナルティの和ではなく最大値なのが。
- 和なら順序の入れ替えができるので話が楽。
- なんらかの貪欲な方法で順序が決まるのだろうか。
- 一番大きなものから取れば良いわけではない
- 初期値100、増加1と、初期値90増加100では後者を先にすべき
- むしろ「次の値が最も大きいものを今回のものとする」が正解？
- しかもペナルティの和ではなく最大値なのが。
- 公式解説
- 仮の「この高さまでに割る」というリミットを用意し、残り時間の少ない順に割る
- 最大化を二分探索でパターン
- f(x)の最大化について直接貪欲法で解く方法が思いつかない時f(x)<Xの解の存在判定問題にすれば「解があるなら最大でなくても良いので1つ見つけよ」になるので貪欲アルゴリズムを見つけやすくなる
- 今回最大値の最小化なのでmaxの不等号は不等号のandによって小さな部分問題に変わる
- max(f(x))<tならf(x)<t
