TopCoder SRM552

ひさしぶりに SRM した

250

一瞬「えっ＞＜」ってなるもちょっと書きだしてみたら（根拠もなしに）N≡0,2 mod 3 のときは全色同じずつ、N≡1 のときは 1 色だけ多くなるだろーって思って二分探索した

500

長方形 2 個選ぶ典型問題。
長方形 O(N^4) 通り全部調べて、「L と P の差」「右端/左端」ごとに可能な最大の面積を記録しておく。その後、右端/左端を拡張する（例えば右端だったら、より右の場所で区切ってもその長方形は使える）。そして、すべての区切り場所ごとに、左と右の差を全部試してくっつける。最後が O(N^5)。スライド最小値使うと O(N^4) でいけるらしいがそんな面倒なことしなくても通る

900

わかんね

結果

Challenge Phase 怖いので無視
oox 609.58 9位

Rating: 2401 -> 2513