- 考えたこと
- 最小カット絡みであることは既知
- アイテムを買うかどうかが二択の選択なのでカットになる
- 比率を最大化する問題を最小カットで解けるのか？
- 比率の最大化を判定問題にして二分探索？
- 最大化を二分探索で
- 複数のアイテムが全部買われていると経験値が入る、をどう表現するのか？
- まず経験値は得なので「複数のアイテムのうち一つでも買ってないなら損失」にする
- 「買ってない」が赤なら、購入コストは素直に辺のる
- 経験値の側はすべての経験値の和Eから実際の経験値eを引いた値になる
- 比率の式を変形する、経験値をe、購入コストをcとすると
- 左辺を最小化した時に負になるなら比率をXより大きくできるということ
- つまりコストの側をX倍して、最小カットを求めた時のカットのコストがE未満なら比率をXより大きくできる
