Codeforces ECR #137 : E. FTL

7問回なのに5問目で割と苦戦。
https://codeforces.com/contest/1743/problem/E

問題

2つの銃があり、それぞれのパワーとリロード時間が与えられる。
敵には耐久力HとシールドSが設定されている。
銃を撃つと、同時に撃ったパワーの総和からSを引いた分だけ耐久力を減らすことができる。
敵の体力を0以下にする最短時間はいくらか。

解法

f(a,b) := 最後に1つ目の銃を撃った時、総ダメージがaで、銃2の残リロード時間がbの状態に至る最短時間
g(a,b) := 最後に2つ目の銃を撃った時、総ダメージがaで、銃1の残リロード時間がbの状態に至る最短時間

aの小さい順、f(a,b)、g(a,b)を埋めて行こう。
aを固定したとき、bに対しf(a,b)やg(a,b)は降順となるケースのみ考えればよい。

ll P[2];
ll T[2];
ll H,S;
map<ll,ll> M1[5050],M2[5050];

ll ret=1LL<<60;
void up1(int h,ll na,ll v) {
	if(h>=H) {
		ret=min(ret,v);
	}
	else {
		if(M1[h].count(na)==0) M1[h][na]=1LL<<60;
		M1[h][na]=min(M1[h][na],v);
	}
}
void up2(int h,ll na,ll v) {
	if(h>=H) {
		ret=min(ret,v);
	}
	else {
		if(M2[h].count(na)==0) M2[h][na]=1LL<<60;
		M2[h][na]=min(M2[h][na],v);
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>P[0]>>T[0];
	cin>>P[1]>>T[1];
	cin>>H>>S;
	
	M1[0][T[1]]=0;
	FOR(i,H) {
		ll pre=1LL<<60;
		FORR2(a,b,M1[i]) {
			if(b>=pre) continue;
			pre=b;
			// laser1
			up1(i+P[0]-S,max(0LL,a-T[0]),b+T[0]);
			// laser2
			up2(i+P[1]-S,max(T[0]-a,0LL),b+a);
			// laserboth
			ll nt=max(T[0],a);
			up1(i+P[0]+P[1]-S,T[1],b+nt);
		}
		pre=1LL<<60;
		FORR2(a,b,M2[i]) {
			if(b>=pre) continue;
			pre=b;
			// laser2
			up2(i+P[1]-S,max(0LL,a-T[1]),b+T[1]);
			// laser2
			up1(i+P[0]-S,max(T[1]-a,0LL),b+a);
			// laserboth
			ll nt=max(T[1],a);
			up1(i+P[0]+P[1]-S,T[1],b+nt);
		}
	}
	cout<<ret<<endl;
}

まとめ

難易度の割に本番AC少ないな。