TopCoder SRM 624 Div1 Easy BuildingHeights、Div2 Medium BuildingHeightsEasy

SRM624に参加。
あと１歩で赤く慣れたのに凡ミスでMediumを落とした…。
3Challengeのおかげでレート増減０で済んだ。
http://community.topcoder.com/stat?c=problem_statement&pm=13211
http://community.topcoder.com/stat?c=problem_statement&pm=13215

問題

N個の配列heights[i]がある。
これらのいくつかの要素に数値を加え、M個以上の要素が同じ値になるようにしたい。

• Div2 Medium ：M個以上の要素が同じ値になるようにするため、必要な加算値の最小値を求めよ。
• Div1 Easy ：M=1～Nのそれぞれに対し、M個以上の要素が同じ値になるようにするため、必要な加算値の最小値を求めてそれらをxorした値を返せ。なお、あるMについて加算したheightsの値は、別のMを考えるときにはいったんリセットされる。

解法

まずheightsを昇順ソートしておく。
heights[x]が最大値となるようにM要素が同じ値にするには、heights[x]*M-(heights[x]+heights[x-1]+...+heights[x-(M-1)])だけ加算すればよい。

後は各xについて上記式の最小値を求めていく。
Div1の場合、Mとxの処理でO(N^2)かかるので、(heights[x]+heights[x-1]+...+heights[x-(M-1)])の値はO(1)で求められるよう事前に累積和を取っておかないとTLEする。

class BuildingHeights {
	public:
	int minimum(vector <int> heights) {
		int sum[4001];
		int N=heights.size();
		int i,v,x;
		int ret=0;
		
		sort(heights.begin(),heights.end());
		ZERO(sum);
		FOR(i,N) sum[i+1]=sum[i]+heights[i];
		FOR(i,N) {
			v=1<<30;
			FOR(x,N) if(x>=i) v=min(v,heights[x]*(i+1)-(sum[x+1]-sum[x-i]));
			ret ^= v;
		}
		return ret;
	}
}

class BuildingHeightsEasy {
	public:
	int minimum(int M, vector <int> heights) {
		int sum[4001];
		int N=heights.size();
		int i,v,x;
		int ret=0;
		
		sort(heights.begin(),heights.end());
		ZERO(sum);
		FOR(i,N) sum[i+1]=sum[i]+heights[i];
		v=1<<30;
		M--;
		FOR(x,N) if(x>=M) v=min(v,heights[x]*(M+1)-(sum[x+1]-sum[x-M]));
		return v;
	}
}

まとめ

なんかCodeforcesに出そうな問題。