kmjp's blog

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

AtCoder ARC #038 : D - 有向グラフと数

うーん、二分探索までは思いついたけどその先が思いつかず。
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;
	
}

まとめ

二分探索思いついた時点でさっさと実装しておけば良かったな。
その後が詰められたかどうかは不明だけど。