yukicoder No.798 - コレクション
自力で解けなかった。悲しい。
Ai + Bi * dという式を見た途端、頭の中がConvex-Hull Trickで支配された。そのせいか、「Biの降順で選ぶのが最適」という簡単な事実にすら気付かなかった。解説をチラ見してこの事実を知ったあとも、無料のものの扱い方がわからなかった。結局解説すべてに目を通すことになった。
証明
「Biの降順で選ぶのが最適」の証明は、蟻本のp.117～118に書かれている。
Biのときに選んだdをDi、Bjのときに選んだdをDjとおき、Bi<BjとDi<Djを満たすとき、DiとDjを入れ替えても何も損をしないことを証明すればいい。つまり以下を示したい。
BiDi + BjDj >= BiDj + BjDi
これを証明するには、右辺を左辺に移動し、左辺の式を変形する。
BiDi + BjDj - BiDj - BjDi
= Bi(Di - Dj) - Bj(Di - Dj)
= (Bi - Bj)(Di - Dj)
= (Bj - Bi)(Dj - Di)
Bi < BjとDi < Djを満たすので、これは正になる。
よって、BiDi + BjDj >= BiDj + BjDiは成り立つ。
このスワップ操作を繰り返すことで、Bを降順に、Dを昇順にすることが最適だとわかる。つまり、既に無料で買うものが決まっているとき、Biの大きいものから購入していくのが最適である。
