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; } }
まとめ
テストケース作るの難しいね。