<p><a href="https://atcoder.jp/contests/arc031/tasks/arc031_4">D - 買い物上手</a>
<img src="https://gyazo.com/50034b043205910e44c64d335da3c8bf/thumb/1000" alt="image"></p>
<ul>
<li>考えたこと<ul>
<li>最小カット絡みであることは既知</li>
<li>アイテムを買うかどうかが二択の選択なのでカットになる</li>
<li>比率を最大化する問題を最小カットで解けるのか？<ul>
<li>比率の最大化を判定問題にして二分探索？</li>
<li><a href="/ja/%E6%9C%80%E5%A4%A7%E5%8C%96%E3%82%92%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2%E3%81%A7">最大化を二分探索で</a></li>
</ul>
</li>
<li>複数のアイテムが全部買われていると経験値が入る、をどう表現するのか？<ul>
<li>まず経験値は得なので「複数のアイテムのうち一つでも買ってないなら損失」にする</li>
<li><img src="https://gyazo.com/490dc64aefcb2601e8db7a000c9a1e36/thumb/1000" alt="image"></li>
</ul>
</li>
<li>「買ってない」が赤なら、購入コストは素直に辺のる</li>
<li>経験値の側はすべての経験値の和Eから実際の経験値eを引いた値$E - e$になる</li>
</ul>
</li>
<li>比率の式を変形する、経験値をe、購入コストをcとすると<ul>
<li>$e/c &gt; X$</li>
<li>$e &gt; cX$</li>
<li>$e - cX &gt; 0$</li>
<li>$cX - e &lt; 0$</li>
<li>左辺を最小化した時に負になるなら比率をXより大きくできるということ</li>
<li>$cX + E - e &lt; E$</li>
<li>つまりコストの側をX倍して、最小カットを求めた時のカットのコストがE未満なら比率をXより大きくできる</li>
</ul>
</li>
</ul>


ARC031D