kmjp's blog

競技プログラミング参加記です

AtCoder ABC #261 : Ex - Game on Graph

DFSをメモ化再帰で通るかと思ったら、通らなかった。
https://atcoder.jp/contests/abc261/tasks/abc261_h

問題

重み付き有向辺で構成されるグラフにおいて、以下の2人制ゲームを考える。
初期状態で頂点Vにコマが置かれる。
以後、2人交互にコマを辺に沿って動かす。途中、コマを動かせなくなったらゲームは終了する。
先手は、通った辺の重みの総和を最小化しようとし、後手は最大化しようとする(無限ループならなおよい)。
両者最適手を取る場合、最終的な辺の重みの総和はどうなるか。

解法

当初のテストケースでは、メモ化再帰のDFSでも通ったようだが、その後テストケースが追加され、通らなくなった。

各点・各人のターンで始めた場合のスコアの最適値を考える。
後退解析を用い、確定済みの頂点からダイクストラの要領で処理しよう。
各点次に先手がコマを動かす場合のスコアを、小さい順に探索して確定させていく。

int N,M,V;
vector<pair<int,int>> E[202020];
int in[202020];
ll X[202020],Y[202020];
int vis[202020];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>V;
	V--;
	FOR(i,N) X[i]=1LL<<60, Y[i]=0;
	
	FOR(i,M) {
		cin>>x>>y>>k;
		x--,y--;
		E[y].push_back({x,k});
		in[x]++;
	}
	priority_queue<pair<ll,int>> Q;
	FOR(i,N) if(in[i]==0) {
		X[i]=Y[i]=0;
		Q.push({0,i});
		FORR2(e2,v2,E[i]) {
			if(chmin(X[e2],Y[i]+v2)) Q.push({-X[e2],e2});
		}
	}
	while(Q.size()) {
		ll co=-Q.top().first;
		int cur=Q.top().second;
		Q.pop();
		if(co!=X[cur]) continue;
		FORR2(e,v,E[cur]) {
			Y[e]=max(Y[e],X[cur]+v);
			if(--in[e]==0) {
				FORR2(e2,v2,E[e]) {
					if(chmin(X[e2],Y[e]+v2)) {
						Q.push({-X[e2],e2});
					}
				}
			}
		}
	}
	
	if(X[V]>1LL<<50) {
		cout<<"INFINITY"<<endl;
	}
	else {
		cout<<X[V]<<endl;
	}
	
}

まとめ

テストケース作るの難しいね。