TopCoder SRM 536 Div2 Hard MergersDivTwo

Hardの割に簡単だと思ったら、Div1 Easyとほぼ同じ問題。
制限は若干違うけど、ほとんど難易度には関係しないし。
http://community.topcoder.com/stat?c=problem_statement&pm=11802

問題

初期状態でN個の企業の価値が整数で与えられる。
M個の企業を合併すると、そのM個の企業は消え、価値がそれらの平均値となる1つの企業になる。
ただし、企業合併はK個以上の企業でしか行えない。

N個の企業に合併を繰り返し、1個の企業にする場合、その価値を最大化せよ。

解法

合併は価値の低い順に行うとよい。
なぜなら合併のたびに個々の企業の価値の影響は、合併した企業数で除算されるので、合併が繰り返されるほど影響が下がる。

よって、まず企業を昇順ソートし、残された企業のうちK個以上の企業を合併した場合の残り企業数と価値でDPすればよい。

なお、Div1 easyではKの制限がなくなるが解法は同じ。

class MergersDivTwo {
	public:
	double findMaximum(vector <int> R, int k) {
		double rev[51];
		int N=R.size(),x,y;
		sort(R.begin(),R.end());
		FOR(x,51) rev[x]=-1e9;
		rev[0]=R[0];
		
		FOR(x,N) {
			double r=rev[x];
			if(r<=-1e9) continue;
			for(y=1;y<=N;y++) {
				if(x+y>=N) break;
				r+=R[x+y];
				if(y+1>=k) rev[x+y]=max(rev[x+y],r/(y+1));
			}
		}
		return rev[N-1];
	}
};

まとめ

なぜDiv1Easy相当が出た…。