表題の問題を解きました。
<問題概要>
N(<=500000)個の美術品があり、大きさと価値が定まっている。
そのうちのいくつかを選ぶとき、(価値の和-(大きさの最大値-大きさの最小値))を最大化せよ。
・方針
とりあえず、大きさの順に並べると、ある区間を選んだときに最大と最小が両端にあって良いので大きさでソートする。
価値の合計をS、最大・最小をAmax,Aminとすると求める値はS-(Amax-Amin)と表せる。
これはAmin+S-Amaxと変形できる(これ重要)
すると、ある美術品を最小値に固定したときに、S-Amaxを最大化すればいいことがわかる。(各美術品が最小値となる場合を考えるとO(N)かかる)
最小値を左から見ていくとき、はじめはSを全体の合計とし、だんだん見終わった部分の値を減らしていく(累積和ですね)とよさそう。
文章力がないので図にしてみる。
PC上で図を書くのが面倒だったので手書きで。
答えの大小関係はS-Amaxの大小関係に依存するので、これの最大値が各美術品が最小となる場合について取得できればいい。
また、この場合は美術品①を最小のものとしている。自分より小さいものを選ばないとすると、範囲がだんだん狭まる。
Q:指定された範囲の最大値を高速で求められるデータ構造ってなーんだ
A:SegmentTree
ということでこれをセグ木に載せましょう。これで前計算O(N)、ある美術品を最小としたときに値の算出がO(logN)で行えます。
あとは最小の美術品を変えたときに値がどう変化するかを追えばいいです。
こうなりますよね。でも、すべてのSを減算していると1回の遷移でO(N)かかってしまい、全体ではO(N^2)かかってしまうのでこれではだめです。
Sの値を変えずに答えを出すことができるんですね、これが。
最大値を求めたあとでそれから今までの累積和を引くことでO(1)ですね。
おしまい。手書き多すぎですみませんね。
今気づきましたが逆からやればセグ木いらないかもね。
提出↓
