Google Code Jam 2014 Round 3 : B. Last Hit

本番Smallしか解けなかったのが惜しい…。
https://code.google.com/codejam/contest/3024486/dashboard#s=p1

問題

N個のモンスターがいる。
距離が近い順に、モンスターのHP(H[i])と得られるゴールド(G[i])が与えられる。

先手と後手が交互にターンを迎えてゲームを行う。
先手は任意の生存モンスターを攻撃するか、もしくは攻撃せずターンをパスすることができる。
モンスターを攻撃する場合、HPをP減少させることができ、攻撃によりHPを0以下にするとG[i]ゴールドを取得できる。

後手は生存するもっとも距離が近いモンスターに攻撃する。
モンスターを攻撃する場合、HPをQ減少させる。
後手の攻撃によりHPを0以下になっても、ゴールドは得られない。

先手が最適手を取った場合、得られるゴールドを最大化せよ。

解法

Smallの場合、N<=4、HP上限200と上限が低いので全員分のHPを状態に持ちメモ化再帰すればよい。

Largeは自力で解法にたどり着けなかったので、kcm1700氏の回答を参考にした。
Largeの場合、状態としてdp[現在見ている敵の番号][後手の攻撃回数][先手の残攻撃回数]=(得られる最大総ゴールド)を持ってDPしていけばよい。

各敵iについて、後手の攻撃回数をjとするとj*Q

int P,Q,N;
int H[105],G[101];
int dpdp[101][11][1001];

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>P>>Q>>N;
	ZERO(H);
	ZERO(G);
	FOR(i,N) cin>>H[i]>>G[i];
	FILL_INT(dpdp,-1000000000);
	dpdp[0][0][1]=0;

	FOR(i,N) {
		for(j=0;j*Q<H[i];j++) {
			// attack?
			FOR(k,1001) {
				if(j*Q+(k-1)*P<H[i] && j*Q+k*P>=H[i]) {
					FOR(x,1001) if(x>=k) {
						dpdp[i+1][0][x-k] = max(dpdp[i+1][0][x-k], dpdp[i][j][x]+G[i]);
					}
				}
			}
			
			// no attack
			FOR(k,1001) {
				if((j+1)*Q>=H[i]) dpdp[i+1][0][k+1] = max(dpdp[i+1][0][k+1], dpdp[i][j][k]);
				else dpdp[i][j+1][k+1] = max(dpdp[i][j+1][k+1], dpdp[i][j][k]);
			}
		}
	}
	
	int ret=0;
	FOR(j,11) FOR(k,1001) ret=max(ret,dpdp[N][j][k]);
	
	_P("Case #%d: %d\n",_loop,ret);
}

まとめ

このDPは本番思いつきたかった…。