うーん、二分探索までは思いついたけどその先が思いつかず。
http://arc038.contest.atcoder.jp/tasks/arc038_d
問題
N頂点M有向辺のグラフが与えられる。
各頂点にはスコアX[i]がふられている。
頂点1から始め、2人で交互に以下のいずれかの処理を行うゲームを考える。
- 移動可能な有向辺がある場合、その先に移動する。
- 現在の頂点でゲームを終了する。その頂点のスコアがゲームのスコアとなる。
両者ゲーム終了をしない場合、後手が10^9回処理した時点で打ち切りとなり、その頂点のスコアがゲームのスコアとなる。
先手はゲームのスコアを最大化、後手は最小化しようとするとき、ゲームのスコアはどうなるか答えよ。
解法
「ゲームスコアはV点以上になる」というようなVの最小値を二分探索で求める。
各頂点と、その頂点訪問時の手番で合わせてゲームの状態は2*N個ある。
この2*N個の頂点からなるグラフを考える。
(当然先手に相当する頂点からは後手に相当する頂点に辺が伸びる)
B問題同様、基本アイデアは以下の通り。
- 相手が必敗の頂点が1個でもあれば、そこに遷移させれば自分が勝ち。
- 相手が必敗の頂点が1個もなければ負け。
まず以下の頂点は勝敗が確定する。
- 先手に相当する頂点で、スコアがV以上なら先手が勝ち。
- 後手に相当する頂点で、スコアがV未満なら後手が勝ち。
- 移動できる有向辺がない場合、そのスコアによって勝敗が確定。
以後、勝敗が確定した頂点から、BFSやキューを使って逆辺を辿り、上記基本アイデアに則って連鎖的に勝敗を確定させていく。
最終的に最初の先手の頂点の勝敗が確定する。
ただ、途中閉路がある場合に勝敗が確定しない頂点が残る場合がある。
この場合最後に後手の手番で終わるので、「先手が勝ち確定できない頂点で終わる」ということになり、これは先手の負けと見なせる。
int N,M; int X[101000]; vector<int> E[201000],RE[201000]; int col[202000]; int numb[202000]; bool ok(int v) { int i; MINUS(col); ZERO(numb); queue<int> Q; FOR(i,N) { if(X[i]>=v) col[i]=1, Q.push(i); else col[100000+i]=1, Q.push(100000+i); if(E[i].empty()) { if(col[i]==-1) col[i]=0, Q.push(i); if(col[100000+i]==-1) col[100000+i]=0, Q.push(100000+i); } } while(Q.size()) { int cur=Q.front(); Q.pop(); if(col[cur]==0) { // white FORR(r,RE[cur]) if(col[r]==-1) col[r]=1, Q.push(r); } else { // black FORR(r,RE[cur]) if(col[r]==-1 && ++numb[r] == E[r].size()) col[r]=0, Q.push(r); } } return col[0]==1; } void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M; FOR(i,N) cin>>X[i]; while(M--) { cin>>x>>y; x--,y--; E[x].push_back(100000+y); RE[100000+y].push_back(x); E[100000+x].push_back(y); RE[y].push_back(100000+x); } x=1; for(i=29;i>=0;i--) if(ok(x+(1<<i))) x+=1<<i; cout<<x<<endl; }
まとめ
二分探索思いついた時点でさっさと実装しておけば良かったな。
その後が詰められたかどうかは不明だけど。