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;
}