AtCoder ARC #041 : D - 辺彩色

本番解けなかったですが面白かったです。
http://arc041.contest.atcoder.jp/tasks/arc041_d

問題

N頂点M無向辺からなる連結グラフが与えられる。
このグラフの辺に対し、以下の要領で色を塗っていく。

• プレイヤーは任意の始点から始め、辺を辿って行く。任意の点で辿るのをやめることができる。
• 辺を通ったとき、奇数回目の移動なら赤、偶数回目の移動なら青でその辺を塗る。
• 辺を複数回通ることもでき、その場合辺の色は上書きされる。

各辺の色が与えられるとき、そのような塗り方は可能か答えよ。

解法

Editorialを見て解いた。

普通に色を塗る順番を考えると、色の上書きの処理がめんどい。
そこで、終点から遡って考えてみる。
この場合、色は最初通った時点で確定することになる。

以下のように終点を総当たりし、BFSなりDFSなりで各辺の色を所定の色で塗りきれるケースがあるか判定する。

• 最後の移動が奇数手か偶数手かわからないので、遡る際は初手の色を赤青両方総当たりする。
• 各頂点から遷移できるのは、該当する色を持つ辺のみ、というルールで探索する。
• 途中奇数長の閉路を見つけた場合、(閉路をグルグル回って移動回数の偶奇を切り替えることで)閉路外の辺を任意色で塗れるので、閉路を見つけた時点で可能確定。

int N,M;
int A[2020],B[2020],C[2020];
int tar[2020][2020];
int col[2020];
vector<int> E[2020];
int vis[2020],len[2020];

void dfs(int cur,int co,int le) {
	if(len[cur]<0) len[cur]=le;
	else if(abs(le-len[cur])%2) {
		_P("Yes\n");
		exit(0);
	}
	FORR(r,E[cur]) {
		int id=tar[cur][r];
		if(vis[id]) continue;
		if(C[id]==co) {
			vis[id]++;
			dfs(r,co^1,le+1);
		}
	}
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>A[i]>>B[i]>>s;
		A[i]--;B[i]--;
		E[A[i]].push_back(B[i]);
		E[B[i]].push_back(A[i]);
		tar[A[i]][B[i]]=tar[B[i]][A[i]]=i;
		C[i]=(s=="r");
	}
	FOR(i,N) {
		FOR(j,2) {
			ZERO(vis);
			MINUS(len);
			dfs(i,j,0);
			if(count(vis,vis+M,0)==0) return _P("Yes\n");
		}
	}
	_P("No\n");
}

まとめ

先日のSRMのブラシで色塗り問題など、データが上書きされるケースは逆にたどる、というテンプレを身につけねば。