Facebook Hacker Cup 2012 Round2

1SUBMIT/1WAというひどい結果でした。自分の今の実力でTop100に入れるなんて思ってないし、もっと練習しなければと思いました。とりあえず復習してAとBは解けたので簡単な解説を書きます。

Road Removal

先に重要じゃない都市同士を結ぶ道路をすべて採用します。するとグラフが、重要じゃない都市のみで構成される複数の連結成分と複数の重要な都市から成り立つ森になります。前者の連結成分を一つの節点とみなしてクラスカル法のようなことをすればOK。使用するアルゴリズムや実装は簡単だけどどのアルゴリズムを適用すれば良いのかが見えにくいという問題で、個人的には良問だと思います。

view plainprint?

1. const int MAX = 10000;  
2. int par[10000];  
3. int rank[10000];  
4.   
5. void init(int n) {  
6.     REP(i, n) {  
7.         par[i] = i;  
8.         rank[i] = 0;  
9.     }  
10. }  
11.   
12. int find(int x) {  
13.     if (x == par[x])  
14.         return x;  
15.     return par[x] = find(par[x]);  
16. }  
17.   
18. bool same(int x, int y) {  
19.     return find(x) == find(y);  
20. }  
21.   
22. void merge(int x, int y) {  
23.     x = find(x);  
24.     y = find(y);  
25.   
26.     if (x == y)  
27.         return;  
28.     if (rank[x] > rank[y]) {  
29.         par[y] = x;  
30.     } else {  
31.         par[x] = y;  
32.         if (rank[x] == rank[y])  
33.             rank[y]++;  
34.     }  
35. }  
36.   
37. void solve() {  
38.     int T;  
39.   
40.     scanf("%d", &T);  
41.     REP(t, T) {  
42.         int N, M, K;  
43.   
44.         scanf("%d %d %d", &N, &M, &K);  
45.         init(N);  
46.   
47.         int a, b;  
48.         vector<pair<int, int> > road;  
49.         REP(i, M) {  
50.             scanf("%d %d", &a, &b);  
51.             if (min(a, b) >= K)  
52.                 merge(a, b);  
53.             else  
54.                 road.push_back(MP(a, b));  
55.         }  
56.   
57.         int ret = 0;  
58.         REP(i, road.size()) {  
59.             a = road[i].first;  
60.             b = road[i].second;  
61.   
62.             if (same(a, b))  
63.                 ++ret;  
64.             else  
65.                 merge(a, b);  
66.         }  
67.   
68.         printf("Case #%d: %d\n", t+1, ret);  
69.     }  
70. }  

const int MAX = 10000;
int par[10000];
int rank[10000];

void init(int n) {
    REP(i, n) {
        par[i] = i;
        rank[i] = 0;
    }
}

int find(int x) {
    if (x == par[x])
        return x;
    return par[x] = find(par[x]);
}

bool same(int x, int y) {
    return find(x) == find(y);
}

void merge(int x, int y) {
    x = find(x);
    y = find(y);

    if (x == y)
        return;
    if (rank[x] > rank[y]) {
        par[y] = x;
    } else {
        par[x] = y;
        if (rank[x] == rank[y])
            rank[y]++;
    }
}

void solve() {
    int T;

    scanf("%d", &T);
    REP(t, T) {
        int N, M, K;

        scanf("%d %d %d", &N, &M, &K);
        init(N);

        int a, b;
        vector<pair<int, int> > road;
        REP(i, M) {
            scanf("%d %d", &a, &b);
            if (min(a, b) >= K)
                merge(a, b);
            else
                road.push_back(MP(a, b));
        }

        int ret = 0;
        REP(i, road.size()) {
            a = road[i].first;
            b = road[i].second;

            if (same(a, b))
                ++ret;
            else
                merge(a, b);
        }

        printf("Case #%d: %d\n", t+1, ret);
    }
}

Monopoly

Union Findと動的計画の合わせ技です。dp[i][j]に会社iの社長が直属の部下をj人持つときの木の高さの最小値を保持します。あとポイントとなるのは、dp[i][j]の更新を高速に計算するためにminHeight[i]に現時点における会社iが取り得る木の高さの最小値を保存しておくことです。Union Findの一度の操作をO(log(N))とすると、一つの問題はO(N log(N) + ND)で計算できます。

view plainprint?

1. const int INF = 999999999;  
2. const int MAX_N = 30000;  
3. const int MAX_D = 5000;  
4. int dp[MAX_N][MAX_D+1];  
5. int minHeight[MAX_N];  
6. int par[MAX_N];  
7. int rank[MAX_N];  
8.   
9. void init(int n) {  
10.     REP(i, n) {  
11.         par[i] = i;  
12.         rank[i] = 0;  
13.     }  
14. }  
15.   
16. int find(int x) {  
17.     if (x == par[x])  
18.         return x;  
19.     return par[x] = find(par[x]);  
20. }  
21.   
22. void merge(int x, int y) {  
23.     x = find(x);  
24.     y = find(y);  
25.   
26.     if (x == y) return;  
27.     if (rank[x] > rank[y])  
28.         par[y] = x;  
29.     else {  
30.         par[x] = y;  
31.         rank[y]++;  
32.     }  
33. }  
34.   
35. bool same(int x, int y) {  
36.     return find(x) == find(y);  
37. }  
38.   
39. void solve() {  
40.     int T;  
41.     scanf("%d", &T);  
42.   
43.     REP(t, T) {  
44.         int N, D;  
45.         scanf("%d %d", &N, &D);  
46.   
47.         init(N);  
48.         REP(i, N) REP(j, D+1) dp[i][j] = INF;  
49.         REP(i, N) {  
50.             minHeight[i] = 1;  
51.             dp[i][0] = 1;  
52.         }  
53.   
54.         int a, b;  
55.         REP(i, N-1) {  
56.             scanf("%d %d", &a, &b);  
57.             a = find(a-1);  
58.             b = find(b-1);  
59.   
60.             merge(a, b);  
61.             int x = find(a);  
62.             dp[x][0] = INF;  
63.             for (int j = D; j > 0; j--)  
64.                 dp[x][j] = min(max(dp[a][j-1], 1+minHeight[b]),   // a becomes the president  
65.                                max(dp[b][j-1], 1+minHeight[a]));  // b becomes the president  
66.   
67.             minHeight[x] = INF;  
68.             REP(j, D+1)  
69.                 minHeight[x] = min(minHeight[x], dp[x][j]);  
70.         }  
71.   
72.         int ret = INF;  
73.         int x = find(0);  
74.         REP(i, D+1)  
75.             ret = min(ret, dp[x][i]);  
76.   
77.         printf("Case #%d: %d\n", t+1, ret);  
78.     }  
79. }  

const int INF = 999999999;
const int MAX_N = 30000;
const int MAX_D = 5000;
int dp[MAX_N][MAX_D+1];
int minHeight[MAX_N];
int par[MAX_N];
int rank[MAX_N];

void init(int n) {
    REP(i, n) {
        par[i] = i;
        rank[i] = 0;
    }
}

int find(int x) {
    if (x == par[x])
        return x;
    return par[x] = find(par[x]);
}

void merge(int x, int y) {
    x = find(x);
    y = find(y);

    if (x == y) return;
    if (rank[x] > rank[y])
        par[y] = x;
    else {
        par[x] = y;
        rank[y]++;
    }
}

bool same(int x, int y) {
    return find(x) == find(y);
}

void solve() {
    int T;
    scanf("%d", &T);

    REP(t, T) {
        int N, D;
        scanf("%d %d", &N, &D);

        init(N);
        REP(i, N) REP(j, D+1) dp[i][j] = INF;
        REP(i, N) {
            minHeight[i] = 1;
            dp[i][0] = 1;
        }

        int a, b;
        REP(i, N-1) {
            scanf("%d %d", &a, &b);
            a = find(a-1);
            b = find(b-1);

            merge(a, b);
            int x = find(a);
            dp[x][0] = INF;
            for (int j = D; j > 0; j--)
                dp[x][j] = min(max(dp[a][j-1], 1+minHeight[b]),   // a becomes the president
                               max(dp[b][j-1], 1+minHeight[a]));  // b becomes the president

            minHeight[x] = INF;
            REP(j, D+1)
                minHeight[x] = min(minHeight[x], dp[x][j]);
        }

        int ret = INF;
        int x = find(0);
        REP(i, D+1)
            ret = min(ret, dp[x][i]);

        printf("Case #%d: %d\n", t+1, ret);
    }
}