Google Code Jam 2013 Round 1A : B. Manage your Energy

さてB。
割と大雑把な解法で自信がなかったが、何とか通って良かった。
時間を見ると、Al・Bl・Csとここまで半分の時間で通ってるんだよな。
https://code.google.com/codejam/contest/2418487/dashboard#s=p1

問題

最初にEのエネルギーがある。
１日終了時に、エネルギーはR回復する(ただし初期値であるE以上には回復しない)
N日間の各日に1のエネルギーから生成できる製品の価値が与えられるので、N日で生成できる総価値の最大値を求める。

解法(Small)

Eは小さいので、各日に残りのエネルギー量と製品生成量でDPすればよい。
時間はO(NE^2)なので、E=5と小さいSmallでは問題なし。

ll E,R,N;
ll V[10001];
ll DP[10002][101];

void solve(int _loop) {
	int i,j,x,y,z,ne=0;
	
	cin >> E >> R >> N;
	FOR(i,N) V[i]=GETi();
	
	ZERO(DP);
	FOR(x,N) FOR(y,E+1) FOR(z,y+1)
		DP[x+1][min(y-z+R,E)] = max(DP[x+1][min(y-z+R,E)],DP[x][y] + z*V[x]);
	
	ll ma=0;
	FOR(x,E+1) ma=max(ma,DP[N][x]);
	
	_PE("Case #%d: %lld\n",_loop,ma);
}

解法(Large)

LargeではEが大きいので、O(NE^2)もかかる手段は利用できない。
ここで、どの製品も１つ生成するのは１のエネルギーが必要なので、もっとも単価の高い製品に多くのエネルギーを費やせば得であることがわかる。

よって、ある日にちの範囲において、開始時のエネルギー量と終了時の必要エネルギーを引数に取った場合、その日にちの間で最大の価値の日に、終了時エネルギー量を満たせる範囲で最大量の製品を作る、という手段を再帰的に行えばよい。

処理１回あたり１つの最大値を求めて処理するので、O(N^2)かかるがN<=10^4なのと定数項の処理時間は短いので時間はさほど問題ない。

ll E,R,N;
ll V[10001];

ll func(ll se,ll ee,ll st,ll en) {
	ll i;
	ll mal=st;
	if(st>=en) return 0;
	
	for(i=st;i<en;i++) if(V[i]>V[mal]) mal=i;
	
	ll ce=min(se+(1+mal-st)*R,E);
	ll ce2=max(0LL,ee-(en-mal-1)*R);
	if(ce<ce2) return 0;
	return (ce-ce2)*V[mal] + func(se,max(0LL,ce-R),st,mal)+func(ce2,ee,mal+1,en);
	
}

void solve(int _loop) {
	int i,j,x,y,z,ne=0;
	
	cin >> E >> R >> N;
	FOR(i,N) V[i]=GETi();
	
	_PE("Case #%d: %lld\n",_loop,func(E,0,0,N));
}

まとめ

ちょっとややこしい問題だが、すんなり解けて良かった。
こういう問題が解けるようになると、成長が実感できて良いな。