Codeforces ECR #143 : G. Removal Sequences

ボス問の割にコードは長くはない。
https://codeforces.com/contest/1795/problem/G

問題

無向グラフが与えられる。
また各点vにパラメータA[v]が設定されている。

点vの次数がA[v]の場合、vとvにつながる辺を削除する、という処理を行うことを考える。
頂点対(x,y)がniceであるとは、全点を削除できる削除順のうち、x→yの順で削除するものとy→xの順で削除するものが両方あるものをいう。
niceな頂点対は何通りあるか答えよ。

なお、入力において全点を削除できる組み合わせが必ず1つはあることが保証されている。

解法

niceでない頂点対、すなわち順序性のある頂点対を列挙しよう。
1つは削除できる点があることから、適当にBFSで消せる点から消していって問題ない。
このようにして消すパターンを1つ作ろう。

実は、消すパターンを変えることはできても、順序性のある頂点対の相対的な削除順は変えられない。
よって、この消すパターンにおける順序性のある頂点対を数えればよい。

dp(i,x,y) := i番目以降の削除順を考えたとき、xの後にyを消せるかというbool値
とすると、
(i-1)番目に削除する辺がa→bであれば、dp(i-1,a,x) = dp(i,a,x) | dp(i-1,b,x)
となる。愚直にやるとO(N*M)かかるが、bitsetなど使い定数倍高速化すると間に合う。

int T,N,M;
vector<int> E[202020];
int A[202020];
int vis[202020];
ll mask[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>M;
		FOR(i,N) {
			cin>>A[i];
			E[i].clear();
			vis[i]=0;
		}
		FOR(i,M) {
			cin>>x>>y;
			x--,y--;
			E[x].push_back(y);
			E[y].push_back(x);
			A[x]--;
			A[y]--;
		}
		vector<pair<int,int>> Es;
		queue<int> Q;
		FOR(i,N) if(A[i]==0) {
			vis[i]=1;
			Q.push(i);
		}
		while(Q.size()) {
			x=Q.front();
			Q.pop();
			FORR(e,E[x]) if(vis[e]==0) {
				A[e]++;
				Es.push_back({x,e});
				if(A[e]==0) {
					vis[e]=1;
					Q.push(e);
				}
			}
		}
		reverse(ALL(Es));
		ll ret=1LL*N*(N+1)/2;
		for(int L=0;L<N;L+=60) {
			int R=min(N,L+60);
			FOR(i,N) mask[i]=0;
			for(i=L;i<R;i++) mask[i]=1LL<<(i-L);
			FORR2(a,b,Es) mask[a]|=mask[b];
			FOR(i,N) ret-=__builtin_popcountll(mask[i]);
		}
		cout<<ret<<endl;
		
		
		
	}
}

まとめ

変なテクは使わないものの、思い付きにくいな…。