Google Code Jam 2022 Round 1A : C. Weightlifting

手間取ったけどどうにか解けた。
https://codingcompetitions.withgoogle.com/codejam/round/0000000000877ba5/0000000000aa9280

問題

E人の人がトレーニングをする。
各人はW種類の重りをそれぞれいくつか重ね、トレーニングをする。
重りはスタック状に積み重ねて使用し、指定された重りの種類と数であれば積み重ね順は問わない。

E人は連続してトレーニングをするので、前の人が使った重りの一部を残して、自身のトレーニングをしてもよい。
この時、重りの積み重ね順を最適化したとき、積み下ろし回数の最小値を求めよ。

解法

以下、重りを積む回数の最小化を考える。それを2倍すれば積み下ろしの回数になる。

基本的に全部の重りを毎回積んだ値を考え、そこからどれだけ積みをサボれるかを考える。
f(L,R) := 区間[L,R)の人の中でサボれる回数の最大値
とする。
まず1人(L+1=R)の場合は、サボる余地はないのでf(L,R)=0固定である。

2人以上の場合、全員で共通する重りの数をx個としたとき、このx個を一番下に置けば、全員再利用できる。
そのため、2人目以降が積むのをサボれるので、一見(R-L-1)*x回積みをサボれると思うが、ここではx回だけ計上する。

それ以降は、この[L,R)を2つに分割し、それぞれサボる回数の最大化を図ろう。
すなわちL＜M＜RとなるMを総当たりして
f(L,R) = x + max(f(L,M)+f(M,R))
と取ればよい。
先ほど「(R-L-1)*x回積みをサボれると思うが、ここではx回だけ計上する」としたのは、残り(R-L-2)*x回のサボり分は、f(L,M)及びf(M,R)の中で改めて計上されるためである。

int E,W,X[102][102];
int dp[101][101];

int dfs(int L,int R) {
	int del[101]={};
	int y,x;
	
	if(L+1>=R) return 0;
	
	if(dp[L][R]>=0) return dp[L][R];
	
	int ret=0;
	FOR(x,W) {
		del[x]=101;
		for(y=L;y<R;y++) del[x]=min(del[x],X[y][x]);
		ret+=del[x];
	}
	int mi=0;
	
	for(int M=L+1;M<R;M++) mi=max(mi,ret+dfs(L,M)+dfs(M,R));
	return dp[L][R]=mi;
	
}

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	MINUS(dp);
	cin>>E>>W;
	ZERO(X);
	int ret=0;
	FOR(y,E) FOR(x,W) {
		cin>>X[y][x];
		ret+=X[y][x];
	}
	ret-=dfs(0,E);
	
	cout<<"Case #"<<_loop<<": "<<(ret*2)<<endl;
}

まとめ

最初smallだけ解いて、改めてlargeを出したけどちゃんと通ってよかった。