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

2016 Facebook Hacker Cup Round 2

contents

  1. 1. A. Boomerang Decoration
  2. 2. B. Carnival Coins
  3. 3. C. Snakes and Ladders
  4. 4. D. Costly Labels
  5. 5. Solution
    1. 5.1. A. Boomerang Decoration
    2. 5.2. B. Carnival Coins
    3. 5.3. C. Snakes and Ladders
    4. 5.4. D. Costly Labels
      1. 5.4.1. 版本 1
      2. 5.4.2. 版本 2

這一場是凌晨的比賽，因此沒有興趣參與，還是來翻譯一下吧！

A. Boomerang Decoration

要製作回力鏢的雙翼，需要兩個對稱形狀的翼構成，簡單來說是兩個相同字串。給予左翼 $L$ 和右翼 $R$，現在 A 和另一名小夥伴 B 同時更改左翼 $L$，使得 $L = R$，請問最少時間為何。

每一時刻，$A$ 可以選擇 $[0, x]$ 都改變成顏色 $c_1$，而 $B$ 則可以選擇 $[y, n-1]$ 全部變成顏色 $c_2$，要求 $A$ 和 $B$ 的塗色區間不可重疊，意即 $y > x$。

由於每一次塗色是前綴或者後綴，那對於 A 而言，一定是選擇 $x$ 嚴格遞減，反之對於 $y$ 是嚴格遞增，否則之前的操作會白工。藉由上述推測得知，A 和 B 塗色的區間不會重疊，得到最後一定要求左區段和右區段工作時間最大值。

目標找到 A 完成左區段 dpL[0...x] 的最少時間，以及 B 完成 dpR[y...n-1] 的最少時間，最後答案為 min(max(dpL[0...x], dpR[x+1...n-1]))。計算 dpL[] 和 dpR[] 的方法是一樣的，左右相反即可，

由於只能更改左翼，右翼不能更改，那麼一旦改了左翼位置 $x$，事實上要全部變動成右翼，變數個數 $d$ 即是右翼不同的連續相同字符片段。根據貪心策略，若左翼位置 $x$ 和右翼位置 $x$ 相同，則變動費用為 dpL[x] = dpL[x-1]，否則就是 dpL[x] = d。時間複雜度 $\mathcal{O}(n)$。

B. Carnival Coins

參與一場遊戲，獎品無限多個，遊戲規則要求一次投擲 $n$ 硬幣，硬幣出現正面的機率 $P$，只要出現 $K$ 個以上正面即可獲得一份獎品，現在手裡握有 $N$ 個硬幣，你可以邀請很多個小夥伴幫忙參與遊戲，將這 $N$ 枚硬幣分給小夥伴玩。在最佳策略下，請問獲得獎品個數的期望值為何？

現在的目標要找到怎麼分，小夥伴個數不是問題，每一個小夥伴要拿多少枚硬幣是主要問題。定義 dp[i][j] 為投擲 $i$ 枚硬幣恰好 $j$ 枚正面的機率，遞推得到 dp[i][j] = dp[i-1][j-1]*P + dp[i-1][j]*(1-P)。由於大於等於 $K$ 枚只能獲得一份獎品，定義 dpw[i] 為投擲 $i$ 枚硬幣獲得一份獎品的期望值，遞推得到 dpw[i] = sum(dp[i][j]), j >= K。

最後，定義 dpw[i] 為分配 $i$ 枚硬幣給小夥伴的最大期望值個數，得到 dpw[i] = max(dpw[i-j]+dpv[j])。每一步都是 $\mathcal{O}(N^2)$，時間複雜度 $\mathcal{O}(N^2)$。

C. Snakes and Ladders

有一個奇怪的收藏家，收集很多梯子，每一個梯子位於水平位置 $x_i$ 高度為 $H_i$，然而當地特有蛇種喜歡懸掛在兩個等高 $H_p$ 的梯子之間，並且兩個梯子中間的其餘梯子都滿足 $H_r \le H_p$。若蛇懸掛在兩個距離 $L$ 的梯子之間，則需要餵養 $L^2$ 單位的飼料，請問飼主一天要餵多少單位的飼料。

搭配組合的數學計算，由於懸掛的組合保證中間不會有高於兩側，則可以用單調堆完成紀錄，由左而右依序加入梯子，在單調堆中維護梯子高度遞減的位置。由於等高的梯子個數需要合併，否則沒辦法計算 $L$，為了計算 $L^2$。當從左而右加入梯子時，往左找到合法的等高梯子，由於得知 $\sum (X - x_i)^2$，把式子展開得到 $nX^2 - 2X \sum x_i + \sum x_i^2$，因此需要對於每一個高度，要合併 $\sum x_i$ 和 $\sum x_i^2$。

由於每一個元素至多 push 和 pop 一次，時間複雜度 $\mathcal{O}(N)$。

D. Costly Labels

在一棵 $N$ 個節點的無根樹，每一個節點可填入 $K$ 種顏色，對於每一個節點填不同顏色都有不同花費，若一個節點 $u$ 的鄰居中有兩個以上節點顏色相同，則 $u$ 需要額外花費 $P$ 來維持平衡。請問著色的最少花費為何。

若不考慮額外花費 $P$ 這一點，這題就是再簡單不過的貪心。從鴿籠原理知道，若一個點的鄰居大於 $K$ 個，則他必然存在兩個相同顏色的鄰居，一定需要花費 $P$ 維持平衡。由於圖給定一棵樹，自然而然地就設想到樹形 dp，維護子樹的最少花費進行合併。

由於子樹的根著色不用考慮，但方案合併要考慮父節點要著色的方案，因此得到狀態 dp[u][c1][c2] 節點 $u$ 著色 $c_1$，$u$ 的父節點著色 $c_2$。分成兩種狀態轉移，是否要花費 $P$，若 $u$ 花費 $P$，直接合併子樹 $v$ 的最小值 dp[v][?][c1]。若不花費 $P$，勢必要讓子樹都填入不同顏色，由於每一個節點配對顏色花費都不同，最小化著色方案是標準的二分圖帶權匹配，可以用 KM 算法或者是最少費用流完成，只要排除預設 $u$ 的父節點顏色建圖即可，幸好不花費的數值都小於等於 $K$，KM 算法提供 $\mathcal{O}(K^3)$。整體的時間複雜度最慘 $\mathcal{O}(N \times K^2 \times K^3)$。

Solution

A. Boomerang Decoration

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
#include <bits/stdc++.h>
using namespace std;
const int MAXS = 131072;
char sa[MAXS], sb[MAXS];
int Ldp[MAXS], Rdp[MAXS];
int main() {
    int testcase, cases = 0;
    int n;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        scanf("%s %s", sa+1, sb+1);
        
        memset(Ldp, 0, sizeof(Ldp));
        memset(Rdp, 0, sizeof(Rdp));
        
        int c;
        c = 0;
        for (int i = 1; i <= n; i++) {
            if (sb[i] != sb[i-1])
                c++;
            if (sa[i] != sb[i])
                Ldp[i] = c;
            else
                Ldp[i] = Ldp[i-1];
        }
        c = 0;
        for (int i = n, j = 1; i >= 1; i--, j++) {
            if (sb[i] != sb[i+1])
                c++;
            if (sa[i] != sb[i])
                Rdp[j] = c;
            else
                Rdp[j] = Rdp[j-1];
        }
        int ret = n;
        for (int i = 1; i <= n; i++) {
            ret = min(ret, max(Ldp[i], Rdp[n-i]));
        }
        printf("Case #%d: %d\n", ++cases, ret);
    }
    return 0;
}

B. Carnival Coins

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
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 4096;
double dp[MAXN][MAXN], dpw[MAXN], dpv[MAXN];
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        int N, K;
        double P;
        scanf("%d %d %lf", &N, &K, &P);
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;
        for (int i = 0; i <= N; i++) {
            for (int j = 0; j <= i; j++) {
                dp[i+1][j] += dp[i][j] * (1-P);
                dp[i+1][j+1] += dp[i][j] * P;
            }
            dpw[i] = 0;
            for (int j = K; j <= i; j++)
                dpw[i] += dp[i][j];
        }
        
        memset(dpv, 0, sizeof(dpv));
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= i; j++) {
                dpv[i] = max(dpv[i], dpw[j] + dpv[i-j]);
            }
        }
        
        double ret = dpv[N];
        printf("Case #%d: %.9lf\n", ++cases, ret);
    }
    return 0;
}

C. Snakes and Ladders

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
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
struct State {
    int H;
    long long sum, sqsum, n;
    State(int H, long long sum = 0, 
        long long sqsum = 0, long long n = 0):
        H(H), sum(sum), sqsum(sqsum), n(n) {}
};
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        int n, x, h;
        scanf("%d", &n);
        vector<std::pair<int, int>> A;
        for (int i = 0; i < n; i++) {
            scanf("%d %d", &x, &h);
            A.push_back(make_pair(x, h));
        }
        sort(A.begin(), A.end());
        long long ret = 0;
        stack<State> stk;
        for (int i = 0; i < n; i++) {
            while (!stk.empty() && stk.top().H < A[i].second)
                stk.pop();
            if (!stk.empty() && stk.top().H == A[i].second) {
                State e = stk.top();
                long long X = A[i].first;
                long long N = e.n;
                long long S = N*X%MOD * X%MOD;
                S = (S - X*2%MOD*e.sum%MOD + e.sqsum)%MOD;
                e.sum = (e.sum + X)%MOD;
                e.sqsum = (e.sqsum + X*X%MOD)%MOD;
                e.n++;
                ret = (ret + S)%MOD;
                stk.pop(), stk.push(e);
            } else {
                long long X = A[i].first;
                stk.push(State(A[i].second, X, X*X%MOD, 1));
            }
        }
        ret = (ret + MOD)%MOD;
        printf("Case #%d: %lld\n", ++cases, ret);
    }
    return 0;
}

D. Costly Labels

版本 1

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 128;
const int MAXM = 1048576;
struct Node {
    int x, y, cap;
    int cost;// x->y, v
    int next;
} edge[MAXM];
class MinCost {
public:
    int e, head[MAXN], pre[MAXN], record[MAXN], inq[MAXN];
    int dis[MAXN];
    int n;
    const int INF = 0x3f3f3f3f;
    void Addedge(int x, int y, int cap, int cost) {
        edge[e].x = x, edge[e].y = y, edge[e].cap = cap, edge[e].cost = cost;
        edge[e].next = head[x], head[x] = e++;
        edge[e].x = y, edge[e].y = x, edge[e].cap = 0, edge[e].cost = -cost;
        edge[e].next = head[y], head[y] = e++;
    }
    pair<int, int> mincost(int s, int t) {
        int mncost = 0;
        int flow, totflow = 0;
        int i, x, y;
        while(1) {
        	for (int i = 0; i < n; i++)
        		dis[i] = INF;
            int oo = dis[0];
            dis[s] = 0;
            deque<int> Q;
            Q.push_front(s);
            while(!Q.empty()) {
                x = Q.front(), Q.pop_front();
                inq[x] = 0;
                for(i = head[x]; i != -1; i = edge[i].next) {
                    y = edge[i].y;
                    if(edge[i].cap > 0 && dis[y] > dis[x] + edge[i].cost) {
                        dis[y] = dis[x] + edge[i].cost;
                        pre[y] = x, record[y] = i;
                        if(inq[y] == 0) {
                            inq[y] = 1;
                            if(Q.size() && dis[Q.front()] > dis[y])
                                Q.push_front(y);
                            else
                                Q.push_back(y);
                        }
                    }
                }
            }
            if(dis[t] == oo)
                break;
            flow = 0x3f3f3f3f;
            for(x = t; x != s; x = pre[x]) {
                int ri = record[x];
                flow = min(flow, edge[ri].cap);
            }
            for(x = t; x != s; x = pre[x]) {
                int ri = record[x];
                edge[ri].cap -= flow;
                edge[ri^1].cap += flow;
                edge[ri^1].cost = -edge[ri].cost;
            }
            totflow += flow;
            mncost += dis[t] * flow;
        }
        return make_pair(mncost, totflow);
    }
    void init(int n) {
    	this->n = n;
        e = 0;
        for (int i = 0; i <= n; i++)
            head[i] = -1;
    }
} g;
int N, K, P;
int costG[1024][32];
vector<int> treeG[1024];
long long dp[1024][32];	// dp[subtree: u][color of u: c] = mincost, don't care penalty P
long long dpv[1024];
void dfs(int u, int p) {
    for (int i = 0; i < K; i++)
        dp[u][i] = costG[u][i];
    for (auto &v : treeG[u]) {
        if (v == p)	continue;
        dfs(v, u);
        
        int cost = P;
        for (auto &adj_v : treeG[v]) {
            if (adj_v == u)	continue;
            cost += dpv[adj_v];
        }
        
        if (treeG[v].size() > K) {
            for (int i = 0; i < K; i++)
                dp[u][i] += cost;
        } else {
            // find disjoint-color by maximum weighted matching
            for (int i = 0; i < K; i++) {	// u-color
                int source = 0, sink = treeG[v].size()+K+1;
                g.init(treeG[v].size()+K+2);
                for (int j = 0; j < K; j++) {
                    if (j == i)	continue;
                    g.Addedge(treeG[v].size()+j+1, sink, 1, 0);
                }
                for (int j = 0; j < treeG[v].size(); j++) {
                    int adj_v = treeG[v][j];
                    if (adj_v == u)	continue;
                    for (int k = 0; k < K; k++) {
                        if (k == i)	continue;
                        g.Addedge(j+1, treeG[v].size()+k+1, 1, dp[adj_v][k]);
                    }
                    g.Addedge(source, j+1, 1, 0);
                }
                pair<int, int> mm = g.mincost(source, sink);
                dp[u][i] += min(cost, mm.first);
            }
        }
    }
    dpv[u] = INT_MAX;
    for (int i = 0; i < K; i++)
        dpv[u] = min(dpv[u], dp[u][i]);
}
long long final(int v) {
    int cost = P;
    for (auto &adj_v : treeG[v])
        cost += dpv[adj_v];
    
    if (treeG[v].size() > K)
        return cost;
    // find disjoint-color by maximum weighted matching
    for (int i = 0; i < K; i++) {	// u-color
        int source = 0, sink = treeG[v].size() + K + 1;
        g.init(treeG[v].size()+K+2);
        for (int j = 0; j < K; j++) {
            g.Addedge(j+treeG[v].size()+1, sink, 1, 0);
        }
        for (int j = 0; j < treeG[v].size(); j++) {
            int adj_v = treeG[v][j];
            for (int k = 0; k < K; k++)
                g.Addedge(j+1, treeG[v].size()+k+1, 1, dp[adj_v][k]);
            g.Addedge(source, j+1, 1, 0);
        }
        
        pair<int, int> mm = g.mincost(source, sink);
        cost = min(cost, mm.first);
    }
    return cost;
}
int main() {
    int testcase, cases = 0;	
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d %d", &N, &K, &P);
        for (int i = 1; i <= N; i++) {
            for (int j = 0; j < K; j++) {
                scanf("%d", &costG[i][j]);
            }
        }
        
        for (int i = 1; i <= N; i++)
            treeG[i].clear();
        for (int i = 1; i < N; i++) {
            int x, y;
            scanf("%d %d", &x, &y);
            treeG[x].push_back(y);
            treeG[y].push_back(x);
        }
        
        dfs(1, -1);
        
        long long ret = INT_MAX;
        for (int i = 0; i < K; i++)
            ret = min(ret, dp[1][i]);
        ret += final(1);
        printf("Case #%d: %lld\n", ++cases, ret);
    }
    return 0;
}

版本 2

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 128;
const int MAXM = 1048576;
struct Node {
    int x, y, cap;
    int cost;// x->y, v
    int next;
} edge[MAXM];
class MinCost {
public:
    int e, head[MAXN], pre[MAXN], record[MAXN], inq[MAXN];
    int dis[MAXN];
    int n;
    const int INF = 0x3f3f3f3f;
    void Addedge(int x, int y, int cap, int cost) {
        edge[e].x = x, edge[e].y = y, edge[e].cap = cap, edge[e].cost = cost;
        edge[e].next = head[x], head[x] = e++;
        edge[e].x = y, edge[e].y = x, edge[e].cap = 0, edge[e].cost = -cost;
        edge[e].next = head[y], head[y] = e++;
    }
    pair<int, int> mincost(int s, int t) {
        int mncost = 0;
        int flow, totflow = 0;
        int i, x, y;
        while(1) {
        	for (int i = 0; i < n; i++)
        		dis[i] = INF;
            int oo = dis[0];
            dis[s] = 0;
            deque<int> Q;
            Q.push_front(s);
            while(!Q.empty()) {
                x = Q.front(), Q.pop_front();
                inq[x] = 0;
                for(i = head[x]; i != -1; i = edge[i].next) {
                    y = edge[i].y;
                    if(edge[i].cap > 0 && dis[y] > dis[x] + edge[i].cost) {
                        dis[y] = dis[x] + edge[i].cost;
                        pre[y] = x, record[y] = i;
                        if(inq[y] == 0) {
                            inq[y] = 1;
                            if(Q.size() && dis[Q.front()] > dis[y])
                                Q.push_front(y);
                            else
                                Q.push_back(y);
                        }
                    }
                }
            }
            if(dis[t] == oo)
                break;
            flow = 0x3f3f3f3f;
            for(x = t; x != s; x = pre[x]) {
                int ri = record[x];
                flow = min(flow, edge[ri].cap);
            }
            for(x = t; x != s; x = pre[x]) {
                int ri = record[x];
                edge[ri].cap -= flow;
                edge[ri^1].cap += flow;
                edge[ri^1].cost = -edge[ri].cost;
            }
            totflow += flow;
            mncost += dis[t] * flow;
        }
        return make_pair(mncost, totflow);
    }
    void init(int n) {
    	this->n = n;
        e = 0;
        for (int i = 0; i <= n; i++)
            head[i] = -1;
    }
} g;
int N, K, P;
int costG[1024][32];
vector<int> treeG[1024];
long long dp[1024][32][32];	// dp[subtree: u][color of u: c][color of u'parent: c]
long long dpv[1024][32];
void dfs(int u, int p) {
    for (auto &v : treeG[u]) {
        if (v == p)	continue;
        dfs(v, u);
    }
    
    for (int i = 0; i < K; i++) {
        for (int j = 0; j < K; j++) {
            int cost = costG[u][i] + P;
            for (auto &v : treeG[u]) {
                if (v == p)	continue;
                cost += dpv[v][i];
            }
            dp[u][i][j] = cost;
            
            if (treeG[u].size() > K)
                continue;
                
            int source = 0, sink = treeG[u].size()+K+1;
            g.init(treeG[u].size()+K+2);
            for (int k = 0; k < K; k++) {
                if (k == j && p != -1)	continue;	// parent color
                g.Addedge(treeG[u].size()+k+1, sink, 1, 0);
            }
            int branch = 0;
            for (int it = 0; it < treeG[u].size(); it++) {
                int v = treeG[u][it];
                if (v == p)	continue;
                branch++;
                for (int k = 0; k < K; k++) {
                    if (k == j && p != -1)	continue;
                    g.Addedge(it+1, treeG[u].size()+k+1, 1, dp[v][k][i]);
                }
                g.Addedge(source, it+1, 1, 0);
            }
            
            pair<int, int> mm = g.mincost(source, sink);
            if (mm.second != branch)
                continue;
            dp[u][i][j] = min(dp[u][i][j], (long long) mm.first + costG[u][i]);
        }
    }
    
    for (int i = 0; i < K; i++) {
        dpv[u][i] = INT_MAX;
        for (int j = 0; j < K; j++)
            dpv[u][i] = min(dpv[u][i], dp[u][j][i]);
    }
}
int main() {
    int testcase, cases = 0;	
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d %d", &N, &K, &P);
        for (int i = 1; i <= N; i++) {
            for (int j = 0; j < K; j++) {
                scanf("%d", &costG[i][j]);
            }
        }
        
        for (int i = 1; i <= N; i++)
            treeG[i].clear();
        for (int i = 1; i < N; i++) {
            int x, y;
            scanf("%d %d", &x, &y);
            treeG[x].push_back(y);
            treeG[y].push_back(x);
        }
        
        dfs(1, -1);
        
        long long ret = INT_MAX;
        for (int i = 0; i < K; i++)
            for (int j = 0; j < K; j++)
                ret = min(ret, dp[1][i][j]);
        printf("Case #%d: %lld\n", ++cases, ret);
    }
    return 0;
}