ABC 047 高橋君と見えざる手 / An Invisible Hand

D - 高橋君と見えざる手 / An Invisible Hand
問題文の情報量が多く, 情報を整理するのに時間がかかります. 高橋君が最適に行動したときの利益を1以上下げるために, りんごの価格を操作するというのが趣旨となります. まず高橋君の戦略を考えると, りんごが安い都市でりんごを買い, より価格の高い都市で売る戦略が考えられます. 都市1からNは一方通行であるため, ある都市iに来た時, 1からi-1までのりんごの最小値と都市iのりんごの差額を見て利益の最大値を更新していきます. 最適となるようなりんごの買い方は安い都市でT個買い, 高い都市でT個すべて売ることです. なぜならば, その時点での最安でない場所でりんごを買ってさらに他の場所でりんごを売っても, そのやり方の利益を超えることができないからです. したがって, りんごをいくつ買うかは問題ではなく, りんごを買う都市と売る都市の2つだけ覚えておけばいいことになります. 買う都市と売る都市で, りんごの差額が最大値をとる都市をすべて列挙し, 売る都市のりんごの価格をすべて1下げれば条件を満たせます. 具体的には, 売る都市と買う都市のペアの数が答えになります. すべての都市のりんごの価格が異なっていることから, ややこしく価格の下げ方を考える必要はありません. ある時点までの最小値を知りたいときはpriority_queueが便利です. 計算量はn個へのヒープの挿入がネックとなり$O(nlogn)$となります.
Submission #2903963 - AtCoder Beginner Contest 047