hogecoder

tsutaj 競技プログラミングの記録

TopCoder SRM 720 Div2 Hard: RainbowGraph

するめうめ

tsutaj.hatenablog.com

問題概要

原文 → TopCoder Statistics - Problem Statement

 N 頂点からなる無向グラフがある。頂点にはそれぞれ色  c_i が付いている。

同じ色の頂点は連続して訪れるように (青 → 赤 → 青 みたいに途中で別の色が入るのはダメ) して、 N 個の頂点全てを  1 度ずつ訪れたい。このようなパスの総数を求めよ。

解説

答えとなるパスは、 (色  c_1 の頂点を全て訪れる) → (色  c_1 の頂点から色  c_2 の頂点に移動する) → (色  c_2 の頂点を全て訪れる) → ... のようになっています。

同じ色の頂点をすべて訪れるようなパスの数は、 bit DP で求めることができます。パスの端点を決めたときにそのような通り方が何通りある、という情報を覚えておくと良いです。

これがわかれば、どの色の頂点はすべて訪れたのか・いまいる場所はどこか・いまいる場所に対応する色と同じ頂点はすべて訪れたのか をキーにして bit DP することで、答えを求められます。

頂点集合と現在の頂点の情報があれば、  3 つめの情報はいらないのではと思うかも知れませんが、これだと微妙に 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 ぎりぎりになってしまいましたが、うまく書けばもっとサボれるのかもしれません。