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