2013 TCO Algorithm Round 2B med: ScotlandYard
解法
まず, Jiro 君が今 Ciel さんのいる場所を特定する方法を考えてみます。
Ciel さんは最初, 0, 1, ..., n-1 のいずれかにいる可能性があります。この集合を S としましょう。そこで Ciel さんが "taxi" と言ったとすると, Jiro 君は集合 S を {v | u -> v に taxi で移動できる, かつ u 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; } };