Google Code Jam 2018 Round1A : C. Edgy Baking

これはシンプルながら面白い問題。
https://codejam.withgoogle.com/2018/challenges/0000000000007883/dashboard/000000000002fff7

問題

N個のクッキーがあり、それぞれW[i]*H[i]の矩形の形状をしている。
各クッキーについて、1回だけ重心を通る直線に沿って割ることができる。割らなくてもよい。

全クッキーの辺の総長をPを超えない範囲でPに近づけよ。

解法

まず元の辺の総和である2*(W[i]+H[i])の総和分は割ろうが割るまいが残る。
重心に沿ってクッキーを割ると、最短で2*min(W[i],H[i])、最長で2*hypot(W[i],H[i])だけ辺の長さが増える。
この間の範囲は任意の値を取れる。

ここで最短の方は常に整数であることに着目しよう。
最短の増分の総和をキーとし、最長の増分の総和の最大値をDPで管理しよう。

最短の増分の総和を元の辺長に加えてもPを超えない場合、最大手最長の増分の総和の最大値までは任意の値を取れるので、その範囲で最もPに近い値を取ればよい。

int T,testcase;
int N,P;
double ma[25050];

void solve(int TC) {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>P;
	int tot=0;
	int W,H;
	FOR(i,25010) ma[i]=-1e10;
	ma[0]=0;
	FOR(i,N) {
		cin>>W>>H;
		tot+=2*W+2*H;
		int a=min(W,H);
		double b=hypot(W,H);
		for(j=25000-a;j>=0;j--) ma[j+a]=max(ma[j+a],ma[j]+b);
	}
	
	double best=tot;
	FOR(j,25001) if(tot+2*j<=P && ma[j]>=0) {
		double v=tot+2*ma[j];
		if(v>=P) best=P;
		else best=max(best,v);
	}
	
	return _P("Case #%d: %.12lf\n",TC,best);
}

まとめ

本番考察時間がなかったけど、まともに2:30やってたら解けてたのかなぁ…？