AtCoder ARC #143 : E - Reversi

なんか本番はこれさっくり解いてるな。
https://atcoder.jp/contests/arc143/tasks/arc143_e

問題

木を成す無向グラフが与えられる。
初期状態で、各点にはリバーシの石が置いてあり、それぞれ白黒いずれの面か表かが与えられる。

以下の手順を繰り返して、石を取り除くことを考える。
白い面が表の石を1つ選び、取り除く。その際、隣接点に石が残っていたら、裏返す。

こうして全石を取り除ける場合、選ぶ石の並び順のうち辞書順最小のものを求めよ。

解法

葉頂点に着目すると、葉の石が白なら葉側から、そうでないなら葉ではない方から先に石を取り除く必要がある。
この手順で、葉から順に各辺に対しどちら側から先に石を取り除くべきかを列挙しよう。

あとはトポロジカルソートの要領で石を取り除くだけ。
辞書順最小となるよう、常に選択肢のうち一番番号の小さい頂点を選ぼう。

int N;
set<int> E[202020],E2[202020];
string S,T;
int did[202020];

vector<int> O[202020];
int in[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].insert(y-1);
		E[y-1].insert(x-1);
		E2[x-1].insert(y-1);
		E2[y-1].insert(x-1);
	}
	cin>>S;
	FORR(c,S) c=c=='W';
	T=S;
	
	queue<int> Q;
	FOR(i,N) if(E[i].size()==1) {
		did[i]=1;
		Q.push(i);
	}
	while(Q.size()) {
		int cur=Q.front();
		Q.pop();
		if(E[cur].size()==0) {
			if(S[cur]==0) {
				cout<<-1<<endl;
				return;
			}
			continue;
		}
		int tar=*E[cur].begin();
		E[tar].erase(cur);
		if(did[tar]==0&&E[tar].size()<=1) {
			Q.push(tar);
			did[tar]=1;
		}
		if(S[cur]==1) {
			S[tar]^=1;
			O[cur].push_back(tar);
			in[tar]++;
		}
		else {
			O[tar].push_back(cur);
			in[cur]++;
		}
	}
	
	vector<int> P;
	set<int> cand;
	FOR(i,N) if(in[i]==0) cand.insert(i);
	while(cand.size()) {
		int cur=*cand.begin();
		cand.erase(cur);
		assert(T[cur]==1);
		FORR(e,E2[cur]) T[e]^=1;
		P.push_back(cur+1);
		FORR(e,O[cur]) {
			in[e]--;
			if(in[e]==0) cand.insert(e);
		}
	}
	if(P.size()!=N) {
		cout<<-1<<endl;
	}
	else {
		FORR(p,P) cout<<p<<" ";
		cout<<endl;
	}
	
		
}

まとめ

なんでBにあんな苦労したんだろ。