Codeforces ECR #155 : F. Last Man Standing

これも結構苦戦している。
https://codeforces.com/contest/1879/problem/F

問題

N人のヒーローがおり、それぞれのHPと防御力が与えられる。
今ここでダメージ量Xを正整数で任意に選んだとする。

毎ターン、ヒーローは以下のようにダメージを受ける。

• 現防御力がXより大きいなら、現防御力からXを引く
• そうでないなら、防御力が初期値に戻るがHPが1減る。HPが0になったヒーローは死亡する。

最適にXを選んだ時、各ヒーローが単独で生き残るターン数の最大値をそれぞれ求めよ。

解法

Xを1からmax(防御力)の範囲で総当たりすることを考える。
各人の生き残りターン数はceil(防御力/X)*HPである。
そこで、ceil(防御力/X)が一致するものはグループとして扱い、sparse tableを使って各グループでHPが最大及び2番手となるヒーローを求めよう。

int T,N,H[202020],A[202020];

ll ret[202020];
pair<pair<int,int>,pair<int,int>> dp[18][505050];

ll turn(int s,int i) {
	if(i<0) return 0;
	return 1LL*(A[i]+s-1)/s*H[i];
}

pair<pair<int,int>,pair<int,int>> merge(pair<pair<int,int>,pair<int,int>> L,pair<pair<int,int>,pair<int,int>> R) {
	if(L.first==R.first) R.first={0,0};
	if(L.first==R.second) R.second={0,0};
	if(L.second==R.first) R.first={0,0};
	if(L.second==R.second) R.second={0,0};
	if(R.first>L.first) swap(R.first,L.first);
	if(R.first>L.second) swap(R.first,L.second);
	if(R.second>L.second) swap(R.second,L.second);
	return L;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		ZERO(dp);
		
		cin>>N;
		FOR(i,N) cin>>H[i+1];
		FOR(i,N) cin>>A[i+1];
		
		FOR(i,N) {
			ret[i+1]=0;
			pair<int,int> p={H[i+1],i+1};
			if(p>dp[0][A[i+1]].first) swap(dp[0][A[i+1]].first,p);
			if(p>dp[0][A[i+1]].second) swap(dp[0][A[i+1]].second,p);
		}
		
		FOR(i,17) {
			FOR(j,500000) {
				if(j+(1<<i)<=500000) dp[i+1][j]=merge(dp[i][j],dp[i][j+(1<<i)]);
				else dp[i+1][j]=dp[i][j];
			}
		}
		
		
		x=0;
		for(i=1;i<=200000;i++) {
			while(1<<(x+1)<=i) x++;
			
			pair<ll,int> ma={};
			pair<ll,int> ma2={};
			
			for(j=1;j<=200000;j+=i) {
				auto C=merge(dp[x][j],dp[x][j+i-(1<<x)]);
				pair<ll,int> a={turn(i,C.first.second),C.first.second};
				pair<ll,int> b={turn(i,C.second.second),C.second.second};
				if(a>ma) swap(a,ma);
				if(a>ma2) swap(ma2,a);
				if(b>ma2) swap(b,ma2);
			}
			chmax(ret[ma.second],ma.first-ma2.first);
		}
		
		FOR(i,N) _P("%lld ",ret[i+1]);
		_P("\n");
		
		
	}
}

まとめ

聞いてしまえば割とシンプルなのだけどね。