Codeforces #930 : Div1 C. Pokémon Arena

あまり面白くはないな…。
https://codeforces.com/contest/1936/problem/C

問題

N体のポケモンがおり、それぞれM種のパラメータを持つ。
ポケモンを2体対戦させる場合、1種類でも相手と同等以上のパラメータを持っていれば勝つことができる。

初期状態で1番のポケモンがアリーナにいる。
ここで以下の処理を行える。

• 指定したポケモンの指定したパラメータをKだけ増やす。その際、コストがKかかる。
• アリーナにいるポケモンに勝てるポケモンで、アリーナのポケモンを差し替える。コストは差し替え先のポケモンに応じてかかる。

N番のポケモンをアリーナに載せるのにかかる最小コストを求めよ。

解法

ポケモンを2回以上差し替える場合、同じパラメータでの比較を連続することは無駄なのでしない。
そのパラメータを変更する作業に、アリーナにポケモンを乗せるコストを対応付けて考えよう。

各ポケモン(W+1)頂点からなるグラフを考える。
以下のように有向辺を張る。

• パラメータ毎にポケモンをパラメータ順に並べ、隣接するポケモンのパラメータ同士を、必要なパラメータ増加コストの辺でつなぐ。
• 各ポケモン、パラメータに対応するW個の各点から、(W+1)個目の点にアリーナに載せるコストの辺を張る。逆に、(W+1)個目の点から、各パラメータに対応するW個の点にコスト0の辺を張る。

これで1番のポケモンの(W+1)個目から、N番のポケモンの(W+1)個目に至る最小コストを求めればよい。

int T,H,W;
int C[404040];
vector<int> A[404040];

vector<ll> dp[404040];
vector<vector<pair<pair<int,int>,int>>> E[404040];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>H>>W;
		FOR(y,H) cin>>C[y];
		
		FOR(y,H) {
			A[y].resize(W);
			FOR(x,W) cin>>A[y][x];
			dp[y].clear();
			E[y].clear();
			dp[y].resize(W+1);
			E[y].resize(W+1);
			FOR(x,W+1) dp[y][x]=1LL<<60;
		}
		FOR(x,W) {
			vector<pair<int,int>> V;
			FOR(y,H) V.push_back({A[y][x],y});
			sort(ALL(V));
			FOR(y,H-1) {
				E[V[y].second][x].push_back({{V[y+1].second,x},0});
				E[V[y+1].second][x].push_back({{V[y].second,x},V[y+1].first-V[y].first});
			}
			FOR(y,H) {
				E[y][x].push_back({{y,W},C[y]});
				E[y][W].push_back({{y,x},0});
			}
		}
		dp[0][W]=0;
		priority_queue<pair<ll,pair<int,int>>> Q;
		Q.push({0LL,{0,W}});
		while(Q.size()) {
			ll co=-Q.top().first;
			y=Q.top().second.first;
			x=Q.top().second.second;
			Q.pop();
			if(dp[y][x]!=co) continue;
			FORR2(e,c,E[y][x]) {
				int ty=e.first;
				int tx=e.second;
				if(chmin(dp[ty][tx],co+c)) Q.push({-dp[ty][tx],{ty,tx}});
			}
		}
		cout<<dp[H-1][W]<<endl;
		
	}
}

まとめ

これは割とすんなり解いてる。