AtCoder ARC #079 : F - Namori Grundy

WAがもったいなかった。
http://arc079.contest.atcoder.jp/tasks/arc079_d

問題

N頂点N有向辺のグラフが与えられる。
各辺iはP[i]→iを結んでいるとする。

各頂点vに非負整数A[v]を振るとき、下記条件を満たす振り方は可能か。

• 辺でつながる頂点の両端は同じ値を持ってはいけない。
• 0≦x＜A[v]となる各整数xについて、v→wに辺がありかつA[w]=xとなるものがなければある。

解法

出る辺のない頂点は値が確定するので、トポロジカルソートでそのような頂点は値を確定させていこう。
そうすると閉路中の頂点群は値を確定できない。

さて、両端が循環する数列についてDP等を行う定番テクとして、1箇所値を総当たりで確定させ、以後順次値を確定させていく手法がある。
今回もそれを使おう。

閉路中の頂点vを一つ選択する。
A[v]は実は以下の２つしか候補がない。
Sをvから辺をはられた閉路外の頂点wに置けるA[w]の集合とする。また、閉路内でvから辺を張った先の頂点をxとする。

• A[v]はSに含まれない最小の非負整数
  • この時、A[x]はA[v]以外の値でなければならない
• A[v]はSに含まれない最小から２番目の非負整数
  • この時、A[x]はSに含まれない最小の非負整数でなければならない

A[v]の値として上記2つを両方ためし、A[x]が条件を満たすか判定すればよい。

int N;
int R[202020];
int G[202020];
set<int> S[202020];
int in[202020];

int dfs(int cur,int tar,int cand,int pre,int fir) {
	int hoge=0;
	while(S[cur].count(hoge) || hoge==cand) hoge++;
	if(R[cur]==tar) return (pre==-1 || pre==hoge) && (hoge!=fir);
	return dfs(R[cur],tar,hoge,pre,fir);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>x;
		in[x-1]++;
		R[i]=x-1;
	}
	MINUS(G);
	
	queue<int> Q;
	FOR(i,N) if(in[i]==0) Q.push(i);
	while(Q.size()) {
		x=Q.front();
		Q.pop();
		G[x]=0;
		while(S[x].count(G[x])) G[x]++;
		
		y=R[x];
		in[y]--;
		S[y].insert(G[x]);
		if(in[y]==0) Q.push(y);
	}
	
	FOR(i,N) if(G[i]==-1) {
		int cand=0,pre=-1;
		for(j=0;cand<2;j++) {
			if(S[i].count(j)) continue;
			if(dfs(R[i],i,j,pre,j)) return _P("POSSIBLE\n");
			
			pre=j;
			cand++;
		}
	}
	_P("IMPOSSIBLE\n");
}

まとめ

ARCとはいえ、いつもより赤い参加者が少ない？