Codeforces #278 Div1 A. Fight the Monster

Aはすんなり解けた。変数名間違えて1WAしたけど。
http://codeforces.com/contest/487/problem/A

問題

自分と相手それぞれヒットポイントH、攻撃力A、守備力Dが与えられる。
１ターンごとに、互いに(自分の攻撃力-相手の守備力)分のダメージを相手に与え、その分相手のHPを減少させることができる。

先にHPが0以下になったら負けである。
逆に勝利条件とは、あるターンで自分のHPが残っており、相手のHPが0以下であることである。

ここで、プレイヤーはそれぞれh,a,dのお金を払ってH,A,Dのパラメータを1上げることができる。
相手に勝利するために必要なパラメータを得るための最小費用を答えよ。

解法

H,A,Dは最大でも100以下である。
よってAを200上昇すれば１ターンで確実に相手に勝てるし、Dを100上昇すれば相手からのダメージが0になり負けることはなくなる。
一方、Hは数千上昇しないといけない場合もある。

よってA,Dの上昇量を総当たりし、そこからHの必要上昇量を求めてコストの最小値を求める。
まずAの上昇量が決まると、相手を倒せるターン数tが求まる。
ターン数tが求まれば、１ターンあたりの被ダメージをaとしてHPがt*a+1以上になるようにすればよい。

int H[2],A[2],D[2];
int h,a,d;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H[0]>>A[0]>>D[0];
	cin>>H[1]>>A[1]>>D[1];
	cin>>h>>a>>d;
	
	int mi=1<<29;
	FOR(x,201) FOR(y,201) {
		int at=A[0]+x-D[1];
		int dm=A[1]-(D[0]+y);
		if(at<=0) continue;
		
		if(dm<=0) mi=min(mi,x*a+y*d);
		else {
			int mt=(H[1]+at-1)/at;
			int nh=mt*dm+1;
			mi=min(mi,x*a+y*d+h*max(0,nh-H[0]));
		}
		
	}
	
	cout<<mi<<endl;
}

まとめ

Hの上限を見誤って計算範囲を間違えた人が続出していた。