GCJ Round 1A 2016 Problem C. BFFs
問題
Dashboard - Round 1A 2016 - Google Code Jam
N 人の人がいる。それぞれの人 i には一人特別な存在の人がいて, BFF[i] がそれである。いま, m 人からなる以下の条件を満たすサイクルを作りたい。
- サイクルをなす各人 i の左右いずれかに BFF[i] がいる
m の最大値を求めよ。
解法
Small は, n 個の順列を作って, それぞれについて先頭 i = 2, 3, ..., n 個を選んだサイクルが valid かどうか調べれば OK です。
Large は, サイクルを構成する方法が 2 通りあることを考慮すればいけます。2 通りとは,
- 有向グラフでサイクルを作る
- p -> q, q -> p の関係を満たす (p, q) の組に対して, a -> b -> ... -> p, c -> d -> ... -> q の組を作る
です。
namespace Small { int cycle[100]; bool ok(int n, const vi& bff) { for (int i = 0; i < n; i++) { int ni = (i+1)%n; int bi = (i+n-1)%n; if (bff[cycle[i]] != cycle[ni] && bff[cycle[i]] != cycle[bi]) return false; } return true; } void solve(int N, vi bff) { vi perm(N); for (int i = 0; i < N; i++) perm[i] = i; int ans = 0; do { for (int i = ans+1; i <= N; i++) { for (int j = 0; j < i; j++) cycle[j] = perm[j]; if (ok(i, bff)) ans = max(ans, i); } } while (next_permutation(perm.begin(), perm.end())); cout << ans << endl; } } namespace Large { int depth[1010]; int dfs(int v, int ng, const vector<vi>& rbff) { int ret = 0; for (int u : rbff[v]) if (u!=ng) { ret = max(ret, dfs(u, ng, rbff)); } return ret+1; } void solve(int N, vi bff) { int ans = 0; // cycle で max for (int i = 0; i < N; i++) { memset(depth, -1, sizeof(depth)); depth[i] = 0; int now = i; while (1) { int next = bff[now]; if (depth[next] != -1) { ans = max(ans, depth[now]+1-depth[next]); break; } else { depth[next] = depth[now]+1; now = next; } } } vector<vi> rbff(N); int sum = 0; for (int i = 0; i < N; i++) rbff[bff[i]].push_back(i); for (int i = 0; i < N; i++) for (int j = i+1; j < N; j++) { if (bff[i] != j || bff[j] != i) continue; sum += dfs(i, j, rbff) + dfs(j, i, rbff); } ans = max(ans, sum); cout << ans << endl; } } int main() { cin.tie(0); ios::sync_with_stdio(false); int T; cin >> T; for (int t = 1; t <= T; t++) { cout << "Case #" << t << ": " ; int N; cin >> N; vi bff(N); for (int i = 0; i < N; i++) { cin >> bff[i]; bff[i]--; } Large::solve(N, bff); } return 0; }