TopCoder SRM 720 Div2 Hard RainbowGraph

実装は若干面倒だけど方針は単純。
https://community.topcoder.com/stat?c=problem_statement&pm=14667

問題

無向グラフが与えられる。
各頂点には色が設定されている。
ここで、任意の頂点を始点・終点とし、辺をたどって全頂点を1つずつたどるパスを考える。
なお、同じ色の頂点群は連続してたどらなければならない。

条件を満たすパスは何通りあるか。

解法

まず同色内で全頂点をたどるパスを列挙しよう。
これはBitDPでもよいしnext_permutationで全列挙しても間に合う。

次にBitDPで通過済みの色と最後にいる頂点を状態として、前処理で求めた同色内のパスの組み合わせを使って数え上げていけばよい。

int N;
int mat[101][101];
ll pat[101][101];
vector<int> CE[101];
ll mo=1000000007;
ll dp[1<<10][101];

class RainbowGraph {
	public:
	int countWays(vector <int> color, vector <int> a, vector <int> b) {
		int i,j,x,y;
		
		N=color.size();
		ZERO(mat);
		ZERO(pat);
		ZERO(dp);
		FOR(i,10) CE[i].clear();
		FOR(i,N) CE[color[i]].push_back(i), mat[i][i]=1;
		
		int al=0;
		FOR(i,10) if(CE[i].empty()) al |= 1<<i;
		
		FOR(i,a.size()) mat[a[i]][b[i]]=mat[b[i]][a[i]]=1;
		FOR(i,10) if(CE[i].size()) {
			do {
				FOR(j,CE[i].size()-1) if(mat[CE[i][j]][CE[i][j+1]]==0) break;
				if(j==CE[i].size()-1) {
					pat[CE[i][0]][CE[i].back()]++;
					dp[al | (1<<i)][CE[i].back()]++;
				}
			} while(next_permutation(ALL(CE[i])));
		}
		for(int mask=1;mask<1<<10;mask++) {
			for(int nc=0;nc<10;nc++) if((mask&(1<<nc))==0) {
				FOR(i,N) if(dp[mask][i]) {
					FORR(a,CE[nc]) if(mat[i][a]) FORR(b,CE[nc]) if(pat[a][b]) (dp[mask|(1<<nc)][b] += dp[mask][i]*pat[a][b])%=mo;
				}
			}
		}
		
		ll ret=0;
		FOR(i,N) ret+=dp[(1<<10)-1][i];
		return ret%mo;
	}
}

まとめ

最近Div2 Hardは面白いと思う問題が減ってきたな…良くも悪くも典型寄りな印象。