mayoko’s diary

プロコンとかいろいろ。

2013 TCO Algorithm Round 2B med: ScotlandYard

解法

まず, Jiro 君が今 Ciel さんのいる場所を特定する方法を考えてみます。
Ciel さんは最初, 0, 1, ..., n-1 のいずれかにいる可能性があります。この集合を S としましょう。そこで Ciel さんが "taxi" と言ったとすると, Jiro 君は集合 S を {v | u -> v に taxi で移動できる, かつ u  \in S} に狭めることが出来ます。

これを繰り返していき, S の要素数が 1 になったら, Jiro 君は Ciel さんの位置を特定でき, ゲームが終了するわけです。

これは, 2^n 個の要素を持つグラフで表現することが出来ます。例えば, {0, 1, 3} という集合から, taxi で行ける集合が {1, 2, 4} だったとすると, {0, 1, 3} -> {1, 2, 4} に有向辺が伸びる, という感じですね。

Ciel さんはゲームの長さを最大化したいので, これは最長経路問題になりました。これは, トポロジカルソートを使って解くことが出来ますが, 今のままでは頂点数が多すぎる (2^n になり得る) のでそこを工夫しなければなりません。

大事なのは「頂点が 2 個以上か, そうでないか」だけなので, 頂点としてありえるのを n*n + n に限定しても大丈夫です(頂点 2 つのペアか, 一つの頂点か)。実際, (複数の頂点の集合) -> (複数の頂点の集合) という遷移は, それが複数の頂点の集合になる原因は, たかだか 2 つの頂点の存在に起因するのでこれで大丈夫です。

bool visit(const vector<vi>& g, int v, vector<int>& order, vector<int>& color) {
    color[v] = 1;
    for (int u : g[v]) {
        if (color[u]==2) continue;
        if (color[u]==1) return false;
        if (!visit(g, u, order, color)) return false;
    }
    order.push_back(v); color[v] = 2;
    return true;
}

// トポロジカルソートする
// 返り値が true の時のみ意味を持つ(false の場合は閉路)
bool TopologicalSort(const vector<vi>& g, vector<int>& order) {
    int n = g.size();
    vector<int> color(n);
    for (int u = 0; u < n; u++) if (!color[u] && !visit(g, u, order, color)) return false;
    reverse(order.begin(), order.end());
    return true;
}

void getSet(int u, int v, const vector<string>& trans, vector<vi>& G) {
    vector<int> memo;
    int n = trans.size();
    for (int i = 0; i < n; i++) {
        if (trans[u][i] == 'Y' || trans[v][i] == 'Y') memo.push_back(i);
    }
    int m = memo.size();
    for (int i = 0; i < m; i++) G[u*n+v].push_back(n*n+memo[i]);
    for (int i = 0; i < m; i++) for (int j = i+1; j < m; j++) {
        G[u*n+v].push_back(memo[i]*n+memo[j]);
    }
}

class ScotlandYard {
public:
    int maxMoves(vector <string> taxi, vector <string> bus, vector <string> metro) {
        int n = taxi.size();
        vector<vi> G(n*n+n);
        for (int u = 0; u < n; u++) for (int v = u+1; v < n; v++) {
            getSet(u, v, taxi, G);
            getSet(u, v, bus, G);
            getSet(u, v, metro, G);
        }
        vector<int> order;
        if (!TopologicalSort(G, order)) return -1;
        vector<int> dp(n*n+n);
        for (int v : order) {
            for (int u : G[v]) dp[u] = max(dp[u], dp[v]+1);
        }
        int ret = 0;
        for (int el : dp) ret = max(ret, el);
        return ret;
    }
};