Codeforces #664 Div1 B. Boboniu Walks on Graph

こちらも問題文の理解に手間取った。
https://codeforces.com/contest/1394/problem/B

問題

N点M辺の有向グラフが与えられる。
各辺には異なる重みが設定され、かつ各点の出次数はk以下である。
以下を満たす数列Cは何通りか。

Cはk要素で、i要素目は1以上i以下の値を取る。
点vにいるとき、その次数がnなら、重みがC[n]番目のところに遷移するとする。
任意の頂点uから上記ルールに則って移動すると、uに戻ることができる。

解法

異なる2点u,u'から、同じ点vに到達できるようなことがあってはならない。
なぜならその後vからu・u'の両方に戻ることはできないからである。

このことから、以下のことがわかる。

• uとu'の出自数が同じnなら、C[n]はu→vやu'→vの遷移はいずれも不可
• uとu'の出自数が異なるn,n'を取るなら、u→vの遷移を満たすC[n]及びu→vの遷移を満たすC[n']は同時に成り立ってはならない

あとはCをk!通り総当たりしよう。

int N,M,K;
vector<pair<int,int>> E[202020];
int from[202020][11];

int ng2[11][11];
int ng[11][11][11];
int C[11];
int ret;
void dfs(int cur) {
	if(cur==K+1) {
		int i;
		//for(i=1;i<=K;i++) cout<<C[i];
		//cout<<endl;
		ret++;
		return;
	}
	int i,x;
	for(i=1;i<=cur;i++) {
		if(ng2[cur][i]) continue;
		for(x=1;x<cur;x++) {
			if(ng[cur][i][x]&(1<<C[x])) break;
		}
		if(x<cur) continue;
		C[cur]=i;
		dfs(cur+1);
		
	}
	
	
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>K;
	FOR(i,M) {
		cin>>x>>y>>r;
		E[x-1].push_back({r,y-1});
	}
	FOR(i,N) {
		sort(ALL(E[i]));
		if(E[i].empty()) return _P("0\n");
		FOR(j,E[i].size()) {
			if(from[E[i][j].second][E[i].size()]&(1<<j)) ng2[E[i].size()][j+1]=1;
			from[E[i][j].second][E[i].size()] |= 1<<j;
		}
	}
	
	FOR(i,N) {
		FOR(x,10) if(from[i][x]) {
			//cout<<"!"<<i<<x<<" "<<from[i][x]<<endl;
			FOR(y,10) if(x!=y) {
				FOR(j,x) if(from[i][x]&(1<<j)) ng[x][j+1][y] |= from[i][y]<<1;
			}
		}
	}
	
	/*
	for(x=1;x<=K;x++) {
		for(y=1;y<=x;y++) {
			for(r=1;r<x;r++) cout<<x<<y<<r<<" "<<ng[x][y][r]<<endl;
		}
	}
	*/
	dfs(1);
	cout<<ret<<endl;
	
}

まとめ

昔書いたコードを思い出すのに手間取った…。