kmjp's blog

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

AtCoder AGC #027 : C - ABland Yard

これはすんなり。
https://beta.atcoder.jp/contests/agc027/tasks/agc027_c

問題

各頂点に'A''B'のいずれかが書かれた無向グラフが与えられる。
'A''B'で構成された任意の文字列に対し、同じ頂点・辺の複数回移動を許したうえで、訪問順がその文字列に一致するような経路が存在するか判定せよ。

解法

ある頂点にいるとき、隣接点にA,Bが両方含まれるなら、経路を構築する過程でその頂点に移動してもその時点では問題ないことになる。
逆にそうでない頂点は残すべきでない。

よって、「隣接点にA,Bが両方含まれない」という点を再帰的に削除していこう。
残グラフが空でないなら、それらの頂点にいる限りは常に'A''B'どちらの文字の頂点にも遷移可能なので、すなわち任意の文字列に対応する経路が取れることになる。

この「逆向きに条件に合わない点を削除する」というテク、最近Codeforcesで見たね。
Manthan Codefest'18 : E. Trips - kmjp's blog

int N,M,lef;
string S;
set<int> E[202020];
int A[202020],B[202020];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>S;
	FOR(i,M) {
		cin>>x>>y;
		E[x-1].insert(y-1);
		E[y-1].insert(x-1);
	}
	
	set<int> Q;
	FOR(i,N) {
		FORR(e,E[i]) {
			if(S[e]=='A') A[i]++;
			if(S[e]=='B') B[i]++;
		}
		if(A[i]==0 || B[i]==0) Q.insert(i);
	}
	
	lef=N;
	while(Q.size()) {
		x=*Q.begin();
		Q.erase(Q.begin());
		lef--;
		FORR(e,E[x]) if(e!=x) {
			E[e].erase(x);
			if(S[x]=='A') A[e]--;
			if(S[x]=='B') B[e]--;
			if(A[e]==0 || B[e]==0) Q.insert(e);
		}
	}
	if(lef) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
}

まとめ

これがすんなり思いつけたおかげで、1完大怪我は防いだ気がする。