Codeforces ECR #117 : F. Armor and Weapons

シナジーの効果がだいぶ小さいな…。
https://codeforces.com/contest/1612/problem/F

問題

N個の武器とM個の防具がある。
i番の武器とj番の防具を装備すると、プレイヤーのパワーは(i+j)となる。
ただし一部の組み合わせは特別でシナジーを発揮し、パワーが(i+j+1)となる。
シナジーの一覧は入力で与えられる。

初期状態で1番の武器と1番の防具を持っており、この状態から、N番の武器とM番の武器を手に入れたい。
時間1を掛けると1つ武器または防具を入手できる。ただし、k番の武器または防具を手に入れられるにはパワーがk以上にできる武器・防具を持たなければならない。
N番の武器とM番の防具を手に入れる最小の時間はいくつか。

解法

N≦Mの場合を考える。

シナジーの効果は1しかないので、シナジーのためにあえて弱い武器・防具を手に入れる必要はない。
よって、手に入れるのはその時点で得られる最大パワーの武器または防具である。

dp(t,n) := 時刻tにおいて、所持する武器の最大パワーがnの時、所持する防具の最大パワー

としてdp(t,N)=Mとなる最小のtを求めよう。
基本的に倍々でパワーを増やせるので、tは高々O(log(N+M))程度まで考えれば十分。
dp(t,n)から武器または防具を買う場合を愚直にシミュレートしていけばよい。

int N,M,T;
set<int> S[202020];
int from[202020],to[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>T;
	j=0;
	if(N>M) {
		j=1;
		swap(N,M);
	}
	FOR(i,T) {
		cin>>x>>y;
		if(j) swap(x,y);
		S[x].insert(y);
	}
	
	from[1]=1;
	for(int step=1;;step++) {
		
		for(x=1;x<=N;x++) to[x]=0;
		for(x=1;x<=N;x++) if(from[x]>=1) {
			y=x+from[x];
			if(S[x].count(from[x])) y++;
			chmax(to[min(N,y)],from[x]);
			chmax(to[x],min(y,M));
		}
		for(x=1;x<=N;x++) from[x]=to[x];
		if(from[N]==M) {
			cout<<step<<endl;
			return;
		}
	}
	
}

まとめ

ECRのF問題まで来た割にコード短いな。