第七回 アルゴリズム実技検定 PAST O - コンピュータ
どういう思考で解いたかを書き下します
indexは断わりが無ければ0-indexedです
まず当然ですがコンピュータの性能は買うたびに良くなると考えていいです。
そして、この問題は使うコンピュータの性能ごとに、区間を分割する問題として考える事にします。
例えば全8日で0, 3, 6日目にコンピュータを買う場合
上のようになります。ここで[0, 3)は0以上3未満を意味します
区間dpとして解く事を念頭に必要な情報を考えます。
dp[i]:=i日目の前日までの状態についての最適値として
iにjから遷移することを[j, i)の区間で区切り、i日目に新しいパソコンを買うという事だとします。
さてdp[i]についてインデックス以外に必要そうなものは、前日までに使った金額や前日の終わりに所持していたパソコンの性能などが考えられますが、使った金額だけ持てばいい事が分かります
なぜならi日目まで生き残っている時点で今所持しているパソコンはB(0)~B(i-1)までの最大値だからです(またi日目に買い替えるのでこれより強いパソコンは必要ありません)
iに遷移出来るのはj<iなるjなのでこのdpをセグ木の上で扱い、貰うdpで考えます。
ここで大まかにはdp[i] = min(dp[j] + max(B[0, i)) ) ( j< i)となります。
なぜならjからiに遷移する際に新しく買うパソコンは道中のBの最大値だからです。
しかし一つ問題がありj->iに遷移する際に所持金がマイナスになる場合があります。これはC = dp[j] + max(B[0, i)), とした時にAが使える金額は S = sum(A[0, j+1))なのでC<=Sなら問題ないです。
もし min(dp[j] + max(B[0, i)) )を満たすjで金額がマイナスになる場合はjをセグ木から削除してよいです。j->iに遷移出来ない場合、i<kなるkについてj->kについても遷移出来ないからです。
よってこの問題を整理すると各iについて遷移元のjとして有効なものが出るまで引き続け、有効でない物が出た場合は削除します。
計算量は全体で削除される回数が多くてもN回で各iについて1回updateされるので全体でO(N log N)です
