するめうめ
問題概要
原文 → TopCoder Statistics - Problem Statement
頂点からなる無向グラフがある。頂点にはそれぞれ色 が付いている。
同じ色の頂点は連続して訪れるように (青 → 赤 → 青 みたいに途中で別の色が入るのはダメ) して、 個の頂点全てを 度ずつ訪れたい。このようなパスの総数を求めよ。
解説
答えとなるパスは、 (色 の頂点を全て訪れる) → (色 の頂点から色 の頂点に移動する) → (色 の頂点を全て訪れる) → ... のようになっています。
同じ色の頂点をすべて訪れるようなパスの数は、 bit DP で求めることができます。パスの端点を決めたときにそのような通り方が何通りある、という情報を覚えておくと良いです。
これがわかれば、どの色の頂点はすべて訪れたのか・いまいる場所はどこか・いまいる場所に対応する色と同じ頂点はすべて訪れたのか をキーにして bit DP することで、答えを求められます。
頂点集合と現在の頂点の情報があれば、 つめの情報はいらないのではと思うかも知れませんが、これだと微妙に DAG にならないので、今回はこのような状態の持ち方で解きました。 (工夫すればどうにかなるのかなあ)
ソースコード
class RainbowGraph { public: int colorcnt[15], colorid[15]; int mapping[110], mpinv[10][10]; int adj[110][110], pat[110][110]; int dp2[1 << 10][110][2]; int countWays(vector<int> color, vector<int> a, vector<int> b) { memset(colorid, 0, sizeof(colorid)); memset(adj, 0, sizeof(adj)); memset(pat, 0, sizeof(pat)); memset(colorcnt, 0, sizeof(colorcnt)); memset(mapping, 0, sizeof(mapping)); memset(mpinv, -1, sizeof(mpinv)); int N = color.size(), M = a.size(), colors = 0; for(int i=0; i<N; i++) { if(colorcnt[ color[i] ] == 0) { colorid[ color[i] ] = colors++; } mapping[i] = colorcnt[ color[i] ]; mpinv[ color[i] ][ colorcnt[ color[i] ]++ ] = i; } vector< vector<int> > adj_list(N); for(int i=0; i<M; i++) { int u = a[i], v = b[i]; adj[u][v] = adj[v][u] = 1; adj_list[u].push_back(v); adj_list[v].push_back(u); } // 同じ色の頂点を全部訪れる場合の数 for(int i=0; i<N; i++) { int c = color[i]; vector< vector<int> > dp(1 << 10, vector<int>(10)); dp[1 << mapping[i]][mapping[i]] = 1; for(int bit=0; bit<(1<<colorcnt[c]); bit++) { for(int j=0; j<colorcnt[c]; j++) { int from = mpinv[c][j]; for(int k=0; k<colorcnt[c]; k++) { if(bit >> k & 1) continue; int to = mpinv[c][k]; if(from < 0 || to < 0 || !adj[from][to]) continue; (dp[bit | (1 << k)][k] += dp[bit][j]) %= MOD; } } } for(int k=0; k<colorcnt[c]; k++) { pat[i][mpinv[c][k]] = dp[(1<<colorcnt[c]) - 1][k]; } } // すべての頂点を訪れる場合の数 memset(dp2, 0, sizeof(dp2)); for(int i=0; i<N; i++) dp2[0][i][0] = 1; for(int bit=0; bit<(1<<colors); bit++) { for(int f=1; f>=0; f--) { for(int i=0; i<N; i++) { if(f == 1) { // 同じ色ぜんぶまわった // まだ行ってない色に行こう for(auto j : adj_list[i]) { if(color[i] == color[j]) continue; if(bit >> colorid[ color[j] ] & 1) continue; (dp2[bit][j][0] += dp2[bit][i][1]) %= MOD; } } if(f == 0) { // 同じ色ぜんぶまわってない // ぜんぶまわったときに最後に訪れるところを試そう for(int j=0; j<colorcnt[ color[i] ]; j++) { int to = mpinv[ color[i] ][j]; ll ad = ((ll)dp2[bit][i][0] * pat[i][to]) % MOD; (dp2[bit | (1 << colorid[ color[i] ])][to][1] += ad) %= MOD; } } } } } int ret = 0; for(int i=0; i<N; i++) { (ret += dp2[(1 << colors) - 1][i][1]) %= MOD; } return ret; } };
TLE ぎりぎりになってしまいましたが、うまく書けばもっとサボれるのかもしれません。