解題區/解題區 - 其他題目

2017 Facebook Hacker Cup Round 1

contents

  1. 1. Facebook 2017 Hacker Cup Round 1
    1. 1.1. A. Pie Progress
    2. 1.2. B. Fighting the Zombies
    3. 1.3. C. Manic Moving
    4. 1.4. D. Beach Umbrellas
    5. 1.5. Solution A
    6. 1.6. Solution B
    7. 1.7. Solution C
    8. 1.8. Solution D

感謝小夥伴妮可、茵可熱情支援

Facebook 2017 Hacker Cup Round 1

A. Pie Progress

單身狗的 $N$ 天日子中 (娛樂性質翻譯)，每天晚餐想要一道點心派搭配。每天早晨決定到當地的餅舖採購，每天一定會生產 $M$ 派，每一種派的價格也有所不同，不用考慮派會壞掉的情況，預先庫存保留著吃。為防止不當商人購買數量過多，當天若購買 $K$ 個派，需要額外支付 $K^2$ 的交易手續費，請問採購花費最少為何。

明顯地，每一天的狀態就是採購了多少個派，得到狀態 $\text{dp}[i][j]$ 表示前 $i$ 天總共採購 $j$ 個餅，轉移過程中要保證數量足夠支付每一天，意即只對 $i \le j$ 進行轉移。每一天窮舉購買的數量，窮舉採購的花費時，勢必要先排序每塊派的價格，每次只挑選前幾個小的，時間複雜度 $O(N^2 M)$ 。

$$\begin{align*} dp[i][j] = \left\{\begin{matrix} 0 && i = 0\;, j = 0\\ \min(dp[i-1][j-k-1] + \text{SumC}[k] + (k+1)^2) && i \le j \\ \infty && \text{otherwise} \end{matrix}\right. \end{align*}$$

B. Fighting the Zombies

在 D&D 遊戲，身為一個魔法師要消滅地圖上的殭屍們。一次操作有兩個步驟，第一步驟圈選任意半徑內的所有殭屍，不改變其相對位置將他們進行轉移，第二步驟選擇長寬為 $R$ 的方形內的所有殭屍，請問一次操作最多可以消滅多少殭屍。

從第二步驟中觀察到消滅的大小是固定的，因此圈選半徑會被約束在 $R$ 內，實際上也不用考慮圓，因為方形被包含在圓裏。最後，我們直接求第一步驟的所有方形情況，將內部的殭屍全部移除後，再窮舉一次方形範圍內部的其他殭屍，所有可能取最大值即可。時間複雜度 $O(N^6)$ 。由於 $N \le 50$ ，六分鐘內是可以容忍的。

C. Manic Moving

搬家公司在 $N$ 個城鎮之間服務，貨車司機打算用最小的油量花費依序完成公司給定 $K$ 個訂單。第 $i$ 名客戶要求從 $S_i$ 地搬到 $D_i$ ，貨車一次可以載運兩名客戶的量。根據訂單順序，先來的就要載貨，同理也要先卸貨。

從題目中發現對於順序要求非常嚴苛，定出每一階段的狀態 $dp[i][j][2]$ 表示完成前 $i$ 個訂單、最後停留位置在 $j$ 地，最後的 [2] 表示前一個階段是否已經卸貨。分成兩種方式討論，時間複雜度 $O(KN)$ 。

D. Beach Umbrellas

有 $N$ 個人各自帶著半徑 $R_i$ 的降落傘，在海岸進行降落，岸上有 $M$ 個降落點，每個降落點間隔一公尺，請問有多少種降落方式使得他們不會碰撞。

從題目給的說明中，我們發現到左右兩側的降落點比較特別，因為他們的傘的一部份可能會落在 $M$ 點之外，因此考慮窮舉降落在左右側的所有方法數 $N^2$ ，若要計算固定左右兩側的方法數，可以使用重複組合 H 得到 (滿足 $x_1 + x_2 + \cdots + x_n = Y$ 且每個數皆為非負整數的方法數)。然而，這樣計算方法缺少順序，最後補上排列計數 $(N-2)!$ 。

來講講窮舉左右兩側之後怎麼算出方法數

  • 左右兩側分別為 $R_i$ 和 $R_j$ 的情況
  • 海岸左寬度增加 $R_i$，同理右寬度增加 $R_j$
  • 如此一來，左右變數的情況就能套用重複組合分配 $N$ 個變數，總和為 $M + R_i + R_j$ ，每個變數至少大於等於 $R_i$

特別地，變數 $M$ 過大。在窮舉所有情況中，組合類型最多 $2R$ 種，而非 $N^2$ 種。計算量多到必須預先建表，每一個組合數 $C^{M+?}_{N}$ ，由於底數是固定的，利用區間滑動在 $O(1)$ 轉換 (需要乘法反元素支援)。預先建表的時間 $O(R)$，窮舉部分 $O(N^2 \log R)$ 。

Solution A

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        int N, M;
        scanf("%d %d", &N, &M);
        int dp[305][305] = {};
        const int INF = 0x3f3f3f3f;
        for (int i = 0; i <= N; i++) {
            for (int j = 0; j <= N; j++)
                dp[i][j] = INF;
        }
        
        dp[0][0] = 0;
        for (int i = 0; i < N; i++) {
            int A[305];
            for (int j = 0; j < M; j++)
                scanf("%d", &A[j]);
            sort(A, A+M);
            for (int j = 0, sum = 0; j < M; j++) {
                sum += A[j];
                A[j] = sum;
            }
            for (int j = i; j < N; j++) {
                if (dp[i][j] == INF)
                    continue;
                for (int k = 0; k < M && k+j <= N; k++) {
                    dp[i+1][j+k+1] = min(dp[i+1][j+k+1], dp[i][j] + A[k] + (k+1)*(k+1));
                }
            }
            for (int j = i+1; j <= N; j++)
                dp[i+1][j] = min(dp[i+1][j], dp[i][j]);
        }
        printf("Case #%d: %d\n", ++cases, dp[N][N]);
    }
    return 0;
}

Solution B

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
using namespace std;
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        int N, R;
        scanf("%d %d", &N, &R);
        vector< pair<int, int> > A;
        set<int> SX, SY;
        for (int i = 0; i < N; i++) {
            int x, y;
            scanf("%d %d", &x, &y);
            A.push_back(make_pair(x, y));
            SX.insert(x), SY.insert(y);
        }
        sort(A.begin(), A.end());
        
        int ret = 0;
        for (auto LX : SX) {
            for (auto LY : SY) {
                int cnt = 0;
                vector<int> used(N, 0);
                for (int i = 0; i < N; i++) {
                    if (A[i].first >= LX && A[i].first <= LX+R
                        && A[i].second >= LY && A[i].second <= LY+R)
                    cnt++, used[i] = 1;
                }
                for (auto TX : SX) {
                    for (auto TY: SY) {
                        int dd = 0;
                        for (int i = 0; i < N; i++) {
                            if (used[i])
                                continue;
                            if (A[i].first >= TX && A[i].first <= TX+R
                                && A[i].second >= TY && A[i].second <= TY+R)
                                dd++;
                        }
                        ret = max(ret, dd+cnt);
                    }
                }
            }
        }
        printf("Case #%d: %d\n", ++cases, ret);
    }
    return 0;
}

Solution C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <bits/stdc++.h>
using namespace std;
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        int N, M, K;
        scanf("%d %d %d", &N, &M, &K);
        
        long long g[105][105] = {};
        const long long INF = 1LL<<60;
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++)
                g[i][j] = INF;
            g[i][i] = 0;
        }
        for (int i = 0; i < M; i++) {
            int A, B;
            long long G;
            scanf("%d %d %lld", &A, &B, &G);
            g[A][B] = min(g[A][B], G);
            g[B][A] = min(g[B][A], G);
        }
        
        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++)
                    g[i][j] = min(g[i][j], g[i][k]+g[k][j]);
            }
        }
        
//		for (int i = 1; i <= N; i++) {
//			for (int j = 1; j <= N; j++)
//				printf("%lld ", g[i][j]);
//			puts("");
//		}
        
        int S[5005], D[5005];
        for (int i = 0; i < K; i++)
            scanf("%d %d", &S[i], &D[i]);
        static long long dp[5005][105][2] = {};
        for (int i = 0; i <= K; i++) {
            for (int j = 0; j <= N; j++)
                dp[i][j][0] = INF, dp[i][j][1] = INF;;
        }
        dp[0][1][0] = 0;
        
        for (int i = 0; i < K; i++) {
            int s1 = S[i], d1 = D[i];
            for (int j = 1; j <= N; j++) {
                long long cc;
                cc = g[j][s1]+g[s1][d1];
                dp[i+1][d1][0] = min(dp[i+1][d1][0], dp[i][j][0] + cc);
                cc = g[j][s1];
                dp[i+1][s1][1] = min(dp[i+1][s1][1], dp[i][j][0] + cc);
                
                if (dp[i][j][1] != INF && i > 0) {
                    int sP = S[i-1], dP = D[i-1];
                    cc = g[j][s1]+g[s1][dP];
                    dp[i+1][dP][1] = min(dp[i+1][dP][1], dp[i][j][1] + cc);
                    cc = g[j][s1]+g[s1][dP]+g[dP][d1];
                    dp[i+1][d1][0] = min(dp[i+1][d1][0], dp[i][j][1] + cc);
                }
            }
            
//			for (int j = 1; j <= N; j++)
//				printf("%lld ", dp[i+1][j][0]);
//			puts("");
        }
        
        long long ret = -1;
        for (int i = 1; i <= N; i++) {
            if (dp[K][i][0] != INF)
                ret = max(ret, dp[K][i][0]);
        }
        printf("Case #%d: %lld\n", ++cases, ret);
    }
    return 0;
}

Solution D

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007LL;
void exgcd(long long x, long long y, long long &g, 
	long long &a, long long &b) {
    if (y == 0)
        g = x, a = 1, b = 0;
    else
        exgcd(y, x%y, g, b, a), b -= (x/y) * a;
}
long long inverse(long long x, long long p) {
    long long g, b, r;
    exgcd(x, p, g, r, b);
    if (g < 0)	r = -r;
    return (r%p + p)%p;
}
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        int N, M, R[2048], S = 0, mxR = 0;
        scanf("%d %d", &N, &M);
        for (int i = 0; i < N; i++)
            scanf("%d", &R[i]), S += R[i], mxR = max(mxR, R[i]);
        if (N == 1) {
            printf("Case #%d: %lld\n", ++cases, M);
            continue;
        }
        fprintf(stderr, "%d %d %d\n", N, S, M);
        long long invNplus = 1;
        map<long long, long long> C;
        {
            long long f = 1;
            for (int i = 1; i <= N; i++)
                f = (f * i)%MOD;
            invNplus = inverse(f, MOD);
            
            int l = 1, r = 1;
            f = 1;
            for (int i = M - 2*S; i <= M - 2*S + 2*mxR; i++) {
                int tM = i+N-1;
                if (tM < N)
                    continue;
                int L = tM-N+1, R = tM;
                if (r < L)
                    l = r = f = L;
                while (l < L)
                    f = (f*inverse(l, MOD))%MOD, l++;
                while (r < R)
                    r++, f = (f * r)%MOD;
                C[tM] = (f * invNplus)%MOD;
//				printf("C(%lld %d) = %lld, %lld\n", tM, N, C[tM], f);
            }
        }
        long long ret = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (i == j)
                    continue;
                int tM = M + R[i] + R[j] - 2*S;
                if (tM+N-1 < N)
                    continue;
//				printf("add C(%d %d)\n", tM+N-1, N);
                ret += C[tM+N-1];
                ret %= MOD;
            }
        }
        
        long long f = 1;
        for (int i = 1; i <= N-2; i++)
            f = (f * i)%MOD;
        ret = ret * f;
        ret %= MOD;
        assert(ret >= 0);
        printf("Case #%d: %lld\n", ++cases, ret);
    }
    return 0;
}