Google Code Jam 2017 Round 1C : A. Ample Syrup

C-smallまでは割とすんなり。
https://code.google.com/codejam/contest/3274486/dashboard

問題

N個の円柱形のパンケーキがある。それぞれ半径R(i)と高さH(i)が与えられる。
このうち任意のK個を選択し、半径の大きい順に下から底面の中心が一致するように積み上げたい。

適切なK個を選び、表面積を最大化せよ。

解法

全体の側面積は単純に選んだK個のパンケーキの側面積となるが、上向きの面積は半径の最大値で決まる。
よって、半径が最大となるパンケーキを1つ総当たりし、それ以下の半径のパンケーキのうち、側面積の大きな(K-1)個を選ぼう。
そうするとO(N^2)で解ける。
もう少しうまくやるとO(N logK)でも解けるが、この問題はそこまでは不要。

int N,K;
double R[1010],A[1010];

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	double pi=atan(1)*4;
	cin>>N>>K;
	FOR(i,N) {
		cin>>R[i]>>A[i];
		A[i] = A[i]*R[i]*2*pi;
		R[i] = R[i]*R[i]*pi;
	}
	
	double ma=0;
	FOR(i,N) {
		vector<double> D;
		FOR(j,N) if(i!=j && R[j]<=R[i]) D.push_back(A[j]);
		sort(ALL(D));
		reverse(ALL(D));
		if(D.size()<K-1) continue;
		D.resize(K-1);
		D.push_back(A[i]);
		ma=max(ma,accumulate(ALL(D),0.0)+R[i]);
	}
	
	_P("Case #%d: %.12lf\n",_loop,ma);
}

まとめ

まぁここはまだまだ。