CSAcademy Round #17 : E. Marbles Graph Game

安直にGrundy数に走ってミスした。
https://csacademy.com/contest/round-17/#task/marbles-graph-game

問題

DAGが与えられる。
いくつかの頂点にはトークンが置かれている。

この状態で2名で行うターン制のゲームを行う。
自分のターンでは、すべてのトークンを今いる頂点から出ているいずれかの辺の先の頂点に移動させる。
その際、複数のトークンが同じ頂点に来ても問題ない。
移動できないトークンがある場合、そのターンのプレイヤーの負けとなる。

両者が最適手を取る場合、勝者は先手後手どちらか。

解法

Nimに持ち込みたくなるが、自分はそれをやって失敗した。
今回はDAGなので末端の頂点からさかのぼっていけば、各頂点にトークンがある場合、その時点の手番の人が勝つか負けるかは求めることができる。
すなわち、移動先のいずれかに相手が負ける頂点があるなら、自分の勝ちである。

今回のゲームは、動かせるトークンが残っていても1つでも動かせないトークンがあると負けである。
よって両者は以下のようにトークンを動かす。

• その位置から勝利できるなら、最小ターン数で勝てる頂点に動かす。
• その位置から勝利できないなら、最大ターン数かかる頂点に動かす。

こうすると、各頂点について最小何ターンで勝つか、または最大何ターンで負けるかがわかる。
最初におかれたトークン群のうち、最小勝利ターンと最大敗北ターン数のうち小さい方が先手の結果となる。

int N,M,K;
int P[101010];
vector<int> E[101010],R[101010];
int in[101010];
int win[101010];
int step[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>K;
	FOR(i,K) cin>>P[i], P[i]--;
	FOR(i,M) {
		cin>>x>>y;
		x--,y--;
		E[x].push_back(y);
		R[y].push_back(x);
		in[x]++;
	}
	
	queue<int> Q;
	FOR(i,N) if(in[i]==0) Q.push(i);
	
	while(Q.size()) {
		x=Q.front();
		Q.pop();
		
		FORR(e,E[x]) if(win[e]==0) win[x]=1;
		
		if(win[x]==1) {
			step[x]=1<<20;
			FORR(e,E[x]) if(win[e]==0) step[x]=min(step[x],step[e]+1);
		}
		else {
			FORR(e,E[x]) step[x]=max(step[x],step[e]+1);
		}
		
		FORR(r,R[x]) if(--in[r]==0) Q.push(r);
	}
	
	int fastest=1<<20;
	int slowest=1<<20;
	FOR(i,K) {
		if(win[P[i]]) fastest=min(fastest,step[P[i]]);
		else slowest=min(slowest,step[P[i]]);
	}
	if(fastest<slowest) cout<<"A"<<endl;
	else cout<<"B"<<endl;
	
	
}

まとめ

一見Nimっぽくてそうでないのがフェイントでよい感じ。