TopCoder SRM 624 Div1 Easy BuildingHeights [1人競技プログラミング Advent Calendar 2016 21日目]

この記事は1人競技プログラミング Advent Calendar 2016 21日目の記事です。

問題概要：
TopCoder Statistics - Problem Statement
N(2<=N<=4000)個i番目の建物の高さがheights[i]で与えられる。
建物の高さを自由に追加することが出来る。

x個の建物の高さを同じ高さにする際に追加する必要な高さの最小をA[x]とする。
A[2] xor A[3] xor ... xor A[N]の値を答えよ。

解いた方法：
建物の高さをソートしてしゃくとりっぽく計算する。累積和を取っておくと速くなる。(取らないと多分TLEする？

#include<bits/stdc++.h>

#define MP make_pair
#define PB push_back
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<(n);i++)
#define REP1(i,n) for(int i=1;i<(n);i++)
#define REP2(i,d,n) for(int i=(d);i<(n);i++)
#define RREP(i,n) for(int i=(n);i>=0;i--)
#define CLR(a)      memset((a),0,sizeof(a))
#define MCLR(a)     memset((a),-1,sizeof(a))
#define RANGE(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY))

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<LL> VLL;
typedef pair<int,int> PII;

const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-9;

const int DX[]={1,0,-1,0},DY[]={0,-1,0,1};

class BuildingHeights {
    public:
    vector<int> heights;
    int minimum(vector<int> _heights) {
        heights = _heights;
        int res = 0;
        sort(ALL(heights));
        int memo[4001] = {0};
        REP(i, heights.size()){
            memo[i+1] = memo[i] + heights[i];
        }


        REP1(i, heights.size()){
            int ans = INF;

            int cnt = 0;
            REP(j, heights.size()){
                if(i+j == heights.size()) break;
                int cost = heights[i+j] * i - (memo[i+j] - memo[j]);
                ans = min(ans, cost);
            }

            res = res ^ ans;
        }

        return res;
    }
};