hotpepsiの練習帳

SRM 624

20:15

Div1 Easy (250) BuildingHeights

問題

• 街にある建物の高さが配列で与えられる
• 建物を高くして高さを揃えたい
• M個の建物の高さを揃える最小コストをA[M]とする
• Mが1～Nまでの排他的論理和を求める

方針

• M=1のときはゼロ
• 最大4000個
• O(N^2)は間に合うが、単純ループのO(N^3)は間に合わない
• 高さに合わせるときは、既存のどれかの高さに合わせることになる
• ソートしておく
• 高さをk個揃えるコストから、k+1個揃えるコストが作れるので、O(N^2)で表が作れる
• Passed System Test
• 1次元の累積和だけあれば範囲の和はわかる
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_624/BuildingHeights.cpp

結果

o-- 200.75pts 423rd/794 rating 1571 -> 1573 (+2)

medium450点だけど難しかった。

http://togetter.com/li/679552