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

[Tmt514] Beverage Cup 2 Warmup A - Euler's Criterion

Problem

日本電影《博士熱愛的算式》中，

博士只有八十分鐘的記憶，　　　　　　　　　
一旦超過這個時間，　　　　　　　　　　　　
他的記憶就自動歸零，重新開始。　　　　　　
然而，博士卻用一個簡單的數學公式，　　　　
驗證了愛的永恆。

  • 《博士熱愛的算式》
$$e^{i \pi} + 1 = 0 \\ e^{ix} = cos(x) + i sin(x) \\ e^{i \pi} = cos(\pi) + i sin(\pi) = -1$$

判斷 $a \equiv x^2 (\text{ mod } p)$ 中，$a$ 是否在模 $p$ 下是個平方數。則滿足

$a^{\frac{p-1}{2}} \equiv x^{p-1} \equiv 1 (\text{ mod } p)$

從歐拉定理 $a^{\varphi (p)} \equiv 1 (\text{ mod } p)$ 可以推導得到上述。接著給定一個集合，分別帶入 $a$, $p$ 有多少組合法解。

Sample Input

1
2
3
4
5
2
4
3 5 7 11
5
3 5 7 11 13

Sample Output

1
2
5
7

Solution

窮舉帶入，利用快速冪乘積檢驗之。

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
#include <stdio.h>
long long mpow(long long x, long long y, long long mod) {
    long long ret = 1;
    while (y) {
        if (y&1)
            ret = (ret * x)%mod;
        y >>= 1, x = (x * x)%mod;
    }
    return ret;
}
int main() {
    int testcase;
    int n, p[128];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n); 
        for (int i = 0; i < n; i++)
            scanf("%d", &p[i]);
            
        int ret = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j)
                    continue;
                if (mpow(p[i], (p[j]-1)/2, p[j]) == 1)
                    ret++;
            }
        }
        printf("%d\n", ret);
    }
    return 0;
}
Read More +
解題區/解題區 - 其他題目

SRM 659 Div1 PublicTransitHard

Problem

給一棵樹圖，然後可以放置傳送門與兩地，可以在一地經過傳送門，從另一個地點飛出，請問放置方法有多少種使得最遠兩點移動距離不大於 X。

Solution

看題解作！但我相信仍然是噁心的！

首先需要做樹形 dp 找到最長路徑，保留通過自己子樹最深三條、不通過自己子樹擁有最長路徑。

窮舉所有建設方案 $O(N^2)$，用 $O(log n)$ 時間驗證方案正確性。固定其中一個點 $A$，接著 Dfs 走訪另一點 $B$，$A$ 到 $B$ 之間只會有一條路徑 $A,u_1, u_2, ..., B$，壓縮其中的路徑變成一維，對於中間的每一點找到 hanging value，hanging value 也就是葉子到 u 的最長距離。

假設從 A 到 B 上的點特徵表示成 $(p_0, v_0), (p_1, v_1), (p_2, v_2), ..., (p_n, v_n)$ 其中 $p_i$ 表示從 A 出發的距離，$v_i$ 表示 hanging value。

Example

1
2
3
4
5
6
7
|        |    |         | ...    |
|        |    |    |    |        |
A(u0) - u1 - u2 - u3 - u4 ... - B(un)
|        |    |    |    |        |
|        |    |    |    |
|        |              Y        
|        X

一個 | 表示子樹的距離 1，從上圖中可以得到 $(p_0, v_0) = (0, 4)$, $(p_1, v_1) = (1, 3)$, $(p_2, v_2) = (2, 2)$, $(p_3, v_3) = (3, 2)$, $(p_4, v_4) = (4, 2)$ …

如果要從 u1 分支 X 抵達 u4 分枝 Y，

  • 經過 u1 - u2 - u3 - u4 的最短距離為 $dist = p_4 - p_1 + v_1 + v_4 = 8$
  • 經過 u1 - A - B - un-1 - ... - u4 的最短距離為 $dist = n - p_4 + p_1 + v_1 + v_4$

特別小心下列情況

1
2
3
4
5
6
7
| 
|                 |
A(u0) ---------- u1 - u2 - u3 - u4 ... - B(un)
|                /|
|\              / |\      <---- inner longest path > X, Stop Dfs
| \            /    \
|  \          /      \

假設 $X = 5$ 有可能 $v_i \le 5$ 但是內部的最長路徑本身就超過，就要停止 Dfs。

More

那移動的距離方案為通過、不通過傳送點兩種，任意兩點 p2 > p1，不滿足的方案滿足下列兩等式

  • $p_2 - p_1 + v_1 + v_2 > X$，轉化變成 $v_1 - p_1 > X - p_2 - v_2$
  • $LIM = X - (n - p_2 + p_1 + v_1 + v_2) < 0$，為了檢查不滿足，則 LIM 要最小化，則 $v_1 + p_1$ 要最大化。

根據 Dfs 逐漸加點，將問題轉化成 RMQ (對一條不滿足下的情況下，第二條要盡可能滿足，利用最大值找到最慘情況。)。

檢查從新加入的點 u，則查找區間 $[X-p_2-v_2, \infty]$ 的最大值 $v_i+p_i$，帶入得到 $LIM$。若 $LIM \geq 0$，得到建造方案合法。Dfs 傳遞下去時，另一種 $LIM$ (屏除子樹 $v_i$ 的計算會不同) 將會限制最多再往下 $LIM$ 層 ($LIM$ 相當於說距離限制還差多少，當往後搜索時，路徑上的節點計算出的 $LIM$ 會逐漸減少 1，若發上路徑上的所有 $LIM < 0$ 則不合法。)，超過這個限制會造成不經過 u 的兩點最短路徑大於 X。

最後特別小心，如果子樹內的最長路徑大於 X 也要停止走訪！接著就實作持久化線段樹，要完成噁心的樹走訪下，不同狀態的線段樹恢復與傳遞變化。

Code

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
183
184
185
186
187
188
189
190
191
192
193
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <map>
#include <assert.h>
using namespace std;
class SegementTree {
public:
    struct Node {
        int l, r, lson, rson;
        int mx;
    } node[1048576];
    int nodesize;
    int init(int l, int r) {
        nodesize = 0;
        int root = build(l, r);
        return root;
    }
    int build(int l, int r) {
        if (l > r)  return 0;
        int k = nodesize++;
        node[k].l = l, node[k].r = r, node[k].mx = -9999;
        node[k].lson = node[k].rson = 0;
        if (l == r) return k;
        int m = (l + r)/2;
        node[k].lson = build(l, m);
        node[k].rson = build(m+1, r);
        return k;
    }
    int change(int p, int x, int val) {
        int k = nodesize++;
        node[k] = node[p];
        node[k].mx = max(node[p].mx, val);
        if (node[k].l == node[k].r) return k;
        int m = (node[k].l + node[k].r)/2;
        if (x <= m)
            node[k].lson = change(node[p].lson, x, val);
        else
            node[k].rson = change(node[p].rson, x, val);
        return k;
    }
    int query(int k, int l, int r) {
        if (l <= node[k].l && node[k].r <= r)
            return node[k].mx;
        int m = (node[k].l + node[k].r)/2;
        if (r <= m)
            return query(node[k].lson, l, r);
        else if (l > m)
            return query(node[k].rson, l, r);
        else
        	return max(query(node[k].lson, l, r), query(node[k].rson, l, r));
    }
} segTree;
const int MAXN = 2048;
const int SHIFT = 4096, MAXR = 8192;	
class PublicTransitHard {
public:
    vector<int> g[MAXN];
    int dp[MAXN][3];
    int dp2[MAXN][2];
    int ret1, ret2, limitX, testA;
    void dfs(int u, int p) {
        dp[u][0] = 0, dp[u][1] = 0, dp[u][2] = 0;
        dp2[u][0] = 0, dp2[u][0] = 0;
        for (int i = 0; i < g[u].size(); i++) {
            int v = g[u][i];
            if (v == p)
                continue;
            dfs(v, u);
            int d = dp[v][0]+1;
            if (d > dp[u][2])
                dp[u][2] = d;
            if (dp[u][2] > dp[u][1])
                swap(dp[u][2], dp[u][1]);
            if (dp[u][1] > dp[u][0])
                swap(dp[u][1], dp[u][0]);
                
            d = max(dp[v][0] + dp[v][1], dp2[v][0]);
            if (d > dp2[u][1])
                dp2[u][1] = d;
            if (dp2[u][1] > dp2[u][0])
                swap(dp2[u][0], dp2[u][1]);
        }
    }
    void dfs2(int u, int p, int segId, int depth, int mnLIM) {
        int p2 = depth, v2 = dp[u][0];
        int mx = segTree.query(segId, limitX - p2 - v2 + 1 + SHIFT, MAXR);
        int LIM = limitX - (depth - p2 + mx + v2);
//		printf("query [%d, oo] = %d\n", limitX - p2 - v2 + 1, mx);
//		printf("testA %d - %d, %d %d, LIM = %d, mx = %d\n", testA, u, p2, v2, LIM, mx);
        if (depth > mnLIM)
            return ;
        if (LIM >= 0 && dp[u][0] + dp[u][1] <= limitX && dp2[u][0] <= limitX) {
//			printf("----- connect %d %d, \n", testA, u);
            if (testA == u)	ret1++;
            else			ret2++;
        }
            
        for (int i = 0; i < g[u].size(); i++) {
            int v = g[u][i];
            if (v == p)
                continue;
                
            int d = dp[v][0]+1;
            if (d != dp[u][0])
                v2 = dp[u][0];
            else
                v2 = dp[u][1];
            
            if (d == dp[u][0]) {
                if (dp[u][1] + dp[u][2] > limitX)
                    continue;
            } else if (d == dp[u][1]) {
                if (dp[u][0] + dp[u][2] > limitX)
                    continue;
            } else {
                if (dp[u][0] + dp[u][1] > limitX)
                    continue;
            }
            
            d = max(dp[v][0] + dp[v][1], dp2[v][0]);
            if (d == dp2[u][0]) {
                if (dp2[u][1] > limitX)
                    continue;
            } else {
                if (dp2[u][0] > limitX)
                    continue;
            }
            
            
//			printf("dfs %d %d, update [%d] = %d\n", p2, v2, v2 - p2, v2 + p2);
            int mx = segTree.query(segId, limitX - p2 - v2 + 1 + SHIFT, MAXR);
            int LIM2 = limitX - (depth - p2 + mx + v2);
            int segId3 = segTree.change(segId, v2 - p2 + SHIFT, v2 + p2);
//			printf("dfs %d %d, update [%d] = %d, LIM2 = %d\n", p2, v2, v2 - p2, v2 + p2, LIM2);
            dfs2(v, u, segId3, depth+1, min(mnLIM, depth+LIM2));
        }
    }
    int countValidTeleporters(int N, vector<int> edges, int X) {
        ret1 = ret2 = 0, limitX = X;
        for (int i = 0; i < N; i++)
            g[i].clear();
        
        for (int i = 0; i < edges.size(); i++) {
            int u = i+1, v = edges[i];
            g[u].push_back(v);
            g[v].push_back(u);
        }
        
        for (int A = 0; A < N; A++) {
            dfs(A, -1);
            int root = segTree.init(0, MAXR);
            testA = A;
//			puts("-----");
            dfs2(A, -1, root, 0, 9999);
        }
        return ret1 + ret2/2;
    }	
};
int main() {
    PublicTransitHard test;
//	int N = 4;
//	int edges[] = {0, 1, 2};
//	int X = 1;
//	int N = 3;
//	int edges[] = {0, 0};
//	int X = 2;
//	int N = 6;
//	int edges[] = {0, 0, 0, 1, 1};
//	int X = 2;
//	int N = 7;
//	int edges[] = {0, 1, 0, 1, 2, 4};
//	int X = 3;
    
//	int N = 16;
//	int edges[] = {0, 1, 0, 2, 0, 0, 4, 5, 8, 9, 10, 11, 8, 4, 6};
//	int X = 7;
    
    int N = 56;
    int edges[] = {0, 1, 1, 3, 1, 5, 1, 0, 8, 8, 10, 10, 12, 10, 10, 8, 16, 16, 18, 19, 19, 21, 19, 19, 24, 25, 25, 27, 18, 0, 30, 30, 30, 33, 34, 34, 34, 30, 38, 39, 39, 38, 42, 43, 0, 45, 45, 45, 48, 45, 45, 51, 45, 53, 54};
    int X = 12;
    
    int ret = test.countValidTeleporters(N, vector<int>(edges, edges + N - 1), X);
    printf("%d\n", ret);
    return 0;
}
Read More +
解題區/解題區 - 其他題目

SRM 659 Div1 CampLunch

Problem

有 M 個人連續 N 天都在同一個地方吃飯，請問它們購買餐點方案數。

  • 與當天坐在相鄰附近的人，一起購買雙人分享餐，解決這天。
  • 買一份雙人分享餐，連續吃兩天。
  • 買一份單人餐，解決這天。

Solution

淡淡地憂傷，一個人買雙人分享餐吃兩天 … 不過沒關係，一道插頭 dp，相當於插入 $1 \times 2$ 或 $2 \times 1$ 塞滿盤面。但每一天相鄰的人都不同，因此壓縮 bitmask 狀態會需要變動，統一紀錄 $[1<<M]$ ，表示 $i-bit$ 第 $i$ 個人是否已經解決今天，接著對應 (up = self, left = 查找位置)，滾動數組進行轉移。

可以參照 UVa 11270 的解法。現在要處理的是變化的 colume 填充。

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
#include <stdio.h>
#include <vector>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const long long MOD = 1000000007;
const int MAXN = 17, MAXM = 17;
class CampLunch {
public:
    int dp[2][1<<MAXM];
    int count(int N, int M, vector <string> a) {
        memset(dp, 0, sizeof(dp));
        int flag = 0;
        dp[0][(1<<M)-1] = 1;
        for (int i = 0; i < N; i++) {			
            for (int j = 0; j < M; j++) {
                int p = flag, q = !flag;
                flag = 1 - flag;
                memset(dp[q], 0, sizeof(dp[q]));
                for (int k = (1<<M)-1; k >= 0; k--) {
                    int L, U;
                    int Lid, Uid;
                    int ways = dp[p][k];
                    
                    if (ways == 0)
                        continue;
                    
                    Lid = j == 0 ? -1 : (a[i][j-1] - 'A');
                    Uid = a[i][j] - 'A';
                    L = j == 0 ? 1 : ((k>>(Lid))&1);
                    U = (k>>Uid)&1;
                                        
                    if (L == 0 && U == 1) 	// plan 1, sit next to each other
                        dp[q][k|(1<<Lid)] = (dp[q][k|(1<<Lid)] + ways)%MOD;
                    if (U == 0) 			// plan 2, two consecutive days.
                        dp[q][k|(1<<Uid)] = (dp[q][k|(1<<Uid)] + ways)%MOD;
                    if (U == 1)				// plan 3, single
                        dp[q][k|(1<<Uid)] = (dp[q][k|(1<<Uid)] + ways)%MOD;
                    if (U == 1)				// reserve
                        dp[q][k^(1<<Uid)] = (dp[q][k^(1<<Uid)] + ways)%MOD;
                }
            }
        }
        
        return dp[flag][(1<<M)-1];
    }
};
int main() {
    CampLunch cl;
    string v[] = {"ABC","ABC"};
    int vv = cl.count(2, 3, vector<string>(v, v+2));
    printf("%d\n", vv);
    return 0;
}
/*
 2
2
{"AB","AB"}
*/
Read More +
解題區/解題區 - 其他題目

SRM 659 Div1 ApplesAndOrangesEasy

Problem

給定長度為 $N$ 個序列，在這序列中表示吃蘋果或者是橘子的順序，必須保證的是任意連續區間長度為 $K$ 中，最多只會吃 $K/2$ 個蘋果，已知部分位置一定是蘋果，請問序列中最多有幾個蘋果。

Solution

嘗試要用 $O(N)$ 的貪心解法，弄了快一個小時沒出來。弄 $O(N^2)$ 做一下就過，從尾端開始往前掃，來決定未知的地方 $i$ 是否要放蘋果，假若後綴 $[i, i+K-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
#include <stdio.h> 
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
class ApplesAndOrangesEasy {
public:
    int maximumApples(int N, int K, vector<int> info) {
        const int MAXN = 4096;
        int A[MAXN] = {}, apple = K/2;
        int ret = (int) info.size();
        memset(A, -1, sizeof(A));
        for (int i = 0; i < info.size(); i++)
            A[info[i]] = 1;
        for (int i = N+1; i <= N + K; i++)
            A[i] = 0;
        for (int i = N; i >= 1; i--) {
            int sum = 0;
            for (int j = i; j < i+K; j++)
                sum += A[j] >= 1;
            if (sum < apple && A[i] == -1)
                A[i] = 2, ret++, sum++;
            if (sum > apple) {
                for (int j = i; j < i+K; j++) {
                    if (sum > apple && A[j] == 2) {
                        A[j] = -1, ret--, sum--;
                    }
                }
            }
        }
        return ret;
    }
};
int main() {
    ApplesAndOrangesEasy ap;
    int a[] = {1, 3};
    ap.maximumApples(3, 2, vector<int>(a, a + 2));
    return 0;
}
Read More +
解題區/解題區 - 其他題目

2015 Google Code Jam Round 1C

windows format to linux format 

1
$ awk '{ sub("\r$", ""); print }' out.txt > output.txt

題解

  • A. Brattleship
  • B. Typewriter Monkey
  • C. Less Money, More Problems

［A. Brattleship］

哥哥和弟弟玩遊戲，在一個 R * C 的網格中，弟弟會放置一個 1 * W 水平放置的戰艦，接著哥哥蒙上眼睛，問弟弟說 (x, y) 是否為戰艦的一部分，而弟弟很狡猾，可以在猜測過程中偷偷改答案，想辦法去搬移戰艦，使得哥哥猜測數量最多。請問哥哥至少要多少次才能猜到。

R * C 跟 1 * C 其實是一樣的，哥哥仍然必須猜完所有的行，因此至少花費 (R - 1) * floor(C/W) + LastLine 的花費，LastLine 怎麼求得呢？其一方法是貪心，其二方法是 dp 博弈最小化，由於 C <= 20，使用 2^C 進行博弈 dp 是不錯的選擇 (懶人系列，咱走這裡)。

［B. Typewriter Monkey］

給定猴子 K 個鍵盤按鈕，鍵盤按鈕對應的字母可能會重複，每個按鈕敲擊的機率均勻分布，接著希望猴子敲擊 S 次，統計出現目標長度 L 的字串 (在長度 S 字串中可能會重疊)，當猴子打出一個目標字串就給一條香蕉。人員要準備最慘情況的香蕉個數，請問猴子完成一次後，獎勵猴子後，手上剩餘的香蕉個數的期望值為何？

首先要找出最慘情況的香蕉個數，也就是去找到最大重疊長度 x，暴力搜索即可 (有機會咱們再來談談 KMP)，基本香蕉數量為 1 + (S - L) / (L - x)。接著找到猴子拼出目標字串的期望值，考慮目標字串的起始位置 i 的機率 expect = p(S) * 1^(S - L)，p(S) = \product(uniform(target[i])), i in [1, S - L + 1]
，最後答案顯而易見 = max_banana - expect * (S - L + 1)。

［C. Less Money, More Problems］

給定 D 種不同的面值，每一種面值最多使用 C 次，請問要湊出 [1, V] 之間所有價錢的交易方式，至少要增加幾個新面值。

貪心思路，假設能湊出 [1, S]，則對於新面值 x 而言，可以增加範圍 [1, S + x * C]。將 x 由小排到大，若 S < x - 1 則新增一個面值 S+1 下去，擴張到範圍 [1, S + (S+1) * C] … 如此類推，想辦法湊出 [1, V]。

A code

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
#include <stdio.h> 
#include <string.h>
#include <algorithm>
using namespace std;
int dp[1<<20], R, C, W;
int isEnd(int u) {
    int place = (1<<W)-1;
    int v = 0;
    for (int i = 0; i < C - W; i++) {
        if (((u>>i)&place) == 0) 
            return 0; 
        v = min(v, __builtin_popcount(((u>>i)&place)));
    }
    return W - v;
}
int dfs(int u) {
    if (isEnd(u))
        return isEnd(u);
    if (dp[u] != -1)
        return dp[u];
    int &ret = dp[u];
    ret = 0x3f3f3f3f;
    for (int i = 0; i < C; i++) {
        if ((u>>i)&1)
            continue;
        ret = min(ret, dfs(u|(1<<i)) + 1);
    }
    return ret;
}
int solve() {
    memset(dp, -1, sizeof(dp));
    int v = dfs(0);
    return v + (R-1) * (C/W);
}
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d %d", &R, &C, &W);
        printf("Case #%d: %d\n", ++cases, solve());
    }
    return 0;
}
/*
999
1 5 1
1 10 3
 
3
1 4 2
1 7 7
2 5 1
*/

B code

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
#include <stdio.h> 
#include <string.h>
#include <algorithm>
using namespace std;
int K, L, S;
char keyboard[128], target[128];
double solve() {
    if (L > S)
        return 0;
    int a[128] = {};
    for (int i = 0; i < K; i++)
        a[keyboard[i]]++;
    for (int i = 0; i < L; i++)
        if (a[target[i]] == 0)
            return 0;
            
    double mx_banana = S / L, expect = 1;
    for (int i = 1; i < L; i++) {
        int ok = 1;
        for (int j = 0; target[i+j] && j < L; j++)
            ok &= target[j] == target[i+j];
        if (ok) {
            mx_banana = 1 + (S - L) / (i); 
            break;
        }
    }
    for (int i = 0; i < L; i++)
        expect = (expect * a[target[i]]) / K;
    return mx_banana - expect * (S - L + 1);
}
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d %d", &K, &L, &S);
        scanf("%s %s", keyboard, target);
        
        double ret = solve();
        printf("Case #%d: %lf\n", ++cases, ret);
    } 
    return 0;
}

C code

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 <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int main() {
    int testcase, cases = 0;
    long long C, K, V, x[128];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%lld %lld %lld", &C, &K, &V);
        
        long long sum = 0, ret = 0;
        for (int i = 0; i < K; i++) {
            scanf("%lld", &x[i]);
        }
        for (int i = 0; i < K; i++) {
            while (sum < V && sum < x[i] - 1) {
                ret++;
                long long ncoin = sum + 1;
                sum += ncoin * C;
            }
            sum += x[i] * C;
        }
        while (sum < V) {
            ret++;
            long long ncoin = sum + 1;
            sum += ncoin * C;
        }
        printf("Case #%d: %d\n", ++cases, ret);
    }
    return 0;
}
/*
*/
Read More +
解題區/解題區 - 其他題目

PTC 201504 D Bilibili's Railgun

Problem

科學超電磁砲 御坂美琴 (簡稱 Bilibili)，在學園都市中經常發生事件，每一個事件都會持續好幾天 [si, ei]，解決一個事件需要使用一次電磁砲。但是在一天中若使用 x 次，當天的消耗能量是 x * x (第 i 發能量為 2i - 1)。

為了解決所有事件，請問最少花費為多少。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
4
3
1 3
1 3
1 3
3
2 3
1 2
1 2
5
2 3
1 2
1 2
3 3
3 3
6
2 3
1 2
1 2
3 3
3 3
2 3

Sample Output

1
2
3
4
3
3
9
12

Solution

Version 1

這裡先提供一個 TLE 的作法，之後再來看看如何用增廣路徑的思路。

對這個問題，可以建造最少費用流模型，在點數不大的情況下可以運行，而這一題額外限制能量消耗的線性關係，最少費用流會因為邊數過多造成 TLE。

建造的方案如 source - event - (day, i) - sink，藉由滿流保證每個事件都會被解決，而每個 event 都指派到第 day 天的第 i 發，約束流量為 1 費用 2i - 1 到 sink，保證每一天使用的能量消耗不重複。

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
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <queue>
#include <functional>
#include <deque>
#include <assert.h>
#include <algorithm>
using namespace std;
#define eps 1e-8
#define MAXN 131072
#define MAXM (1048576<<2)
struct Node {
    int x, y, cap;
    double cost;// x->y, v
    int next;
} edge[MAXM];
int e, head[MAXN], pre[MAXN], record[MAXN], inq[MAXN];
int dis[MAXN];
void addEdge(int x, int y, int cap, int cost) {
    assert(x < MAXN && y < MAXN && e < MAXM);
    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++;
}
int mincost(int s, int t, int n) {
    int mncost = 0;
    int flow, totflow = 0;
    int i, x, y;
    int oo = 0x3f3f3f3f;
    while (1) {
        for (int i = 0; i <= n; i++)
            dis[i] = oo;
        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 mncost;
}
int main() {
    int testcase, N, S[1024], E[1024];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &N);
        
        int A[128] = {}, B[128] = {};
        for (int i = 0; i < N; i++) {
            scanf("%d %d", &S[i], &E[i]);
            for (int j = S[i]; j <= E[i]; j++)
                A[j]++;
        }
        
        e = 0;
        memset(head, -1, sizeof(head));
        
        for (int i = 1; i <= 100; i++)
            B[i] = B[i-1] + A[i];
//        printf("%d\n", A[100]);
        int source = N + B[100] + 1, sink = N + B[100] + 2;
//        printf("source %d sink %d\n", source, sink);
        for (int i = 1; i <= 100; i++) {
//            printf("---- %d\n", A[i]);
            for (int j = 0, lj = B[i-1]; j < A[i]; j++, lj++) {
                addEdge(N + lj, sink, 1, j * 2 + 1);
                assert(N + lj < source);
//                printf("%d %d\n", N + lj, sink);
            }
        }
        for (int i = 0; i < N; i++) {
            addEdge(source, i, 1, 0);
            for (int j = S[i]; j <= E[i]; j++) {
                for (int k = 0, lk = B[j-1]; k < A[j]; k++, lk++) {
                    addEdge(i, N + lk, 1, 0);
                }
            }
        }
        
        int ret = mincost(source, sink, sink + 1);
        printf("%d\n", ret);
    }
    return 0;
}

Version 2

使用增廣路徑的想法，依序加入每一個 event 進來，移動 event 發生的時間。

當兩天原本的事件數 event[i] - event[j] = 1，那麼移動 event i 到另一天 j，總花費不會增加。接著可以保證，前 i 個 event 完成時，能夠移動 event 的情況 (直接或間接)，不會發生事件數差異大於等於 2！如果發生這種情況，則前 i 個事件的能量消耗不是最優解。

加入第 i+1 個事件，有機會發生可移動事件的天數之間的事件數差異大於等於 2，若發生這種情況，將其中一個事件移動到那一天執行。由於上述觀察，加入新的事件時，必然選擇可填入的最少能量消耗的日期，再去消除可以遞移的情況。否則會有一個更優解存在。

有沒有可能存在前 i-1 個事件不是最優解，加入第 i 個事件可以變成最優解？答案是否定的，既然不是最優解，一定存在事件數差異大於等於 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
#include <stdio.h> 
#include <assert.h>
#include <algorithm>
#include <string.h>
#include <vector>
#include <set>
using namespace std;
const int MAXN = 1024;
const int MAXD = 105;
struct Time {
    int st, ed;
    bool operator<(const Time &a) const {
        if (st != a.st)	
            return st < a.st;
        return ed < a.ed;
    }
} T[MAXN];
int visited[MAXD], match[MAXN];
vector<int> event[MAXD];
int event_move[MAXD][MAXD];
int dfs(int u, int place) {
    visited[u] = 1;
    if (event[u].size() < place - 1)
        return 1;
    for (int i = 1; i < MAXD; i++) {
        if (!visited[i]) {
            if (event_move[u][i] > 0) { // find a object to move i-day
                if (dfs(i, place)) {
                    int id = -1, id_pos = -1;
                    for (int j = 0; j < event[u].size(); j++) {
                        id = event[u][j], id_pos = j;
                        if (T[id].st <= i && i <= T[id].ed)
                            break;
                    }
                    assert(id >= 0);
                    for (int j = T[id].st; j <= T[id].ed; j++) {
                        event_move[u][j]--;
                        event_move[i][j]++;
                    }
                    match[id] = i;
                    event[u].erase(event[u].begin() + id_pos);
                    event[i].push_back(id);
                    return 1;
                }
            }
        }
    }
    return 0;
}
int main() {
    int testcase, N;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &N);
        for (int i = 0; i < N; i++)
            scanf("%d %d", &T[i].st, &T[i].ed);
        
        memset(event_move, 0, sizeof(event_move));
        for (int i = 0; i < MAXD; i++)
            event[i].clear();
        
        sort(T, T + N);
        for (int i = 0; i < N; i++) {
            int mn_day = T[i].st;
            for (int j = T[i].st; j <= T[i].ed; j++) {
                if (event[j].size() < event[mn_day].size())
                    mn_day = j;
            }
            
            match[i] = mn_day, event[mn_day].push_back(i);
            for (int j = T[i].st; j <= T[i].ed; j++) {
                event_move[mn_day][j]++;
            }			
            
            memset(visited, 0, sizeof(visited));
            dfs(mn_day, event[mn_day].size());
        }
        
        int ret = 0;
//		for (int i = 0; i < N; i++)
//			printf("%d\n", match[i]);
        for (int i = 1; i < MAXD; i++)
            ret += event[i].size() * event[i].size();
        printf("%d\n", ret);
    }
    return 0;
}

Version 3

費用流的做法不難、想法也很簡單，但是速度一直提升不上來，原因是邊數過多，費用流 O(VVE)，最暴力的費用流 E = 10^5、V = 10^5，病急投靠夢月來優化，由於費用流每次增廣流量都為 1，最後一層的邊使用跟回溯只會有兩種，因此將 (day, i) 的狀態縮小為 (day)，接著用特殊邊來可函數的邊花費 (？)，大幅度地降點後，終於來到 E = 10^5、V = 10^3。

深感欣慰的同時 TLE 也來報喜。

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
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <queue>
#include <functional>
#include <deque>
#include <assert.h>
#include <algorithm>
using namespace std;
#define MAXN 2048
#define MAXM (526244)
struct Node {
    int x, y, cap;
    int cost;// x->y, v
    int next, sp;
} edge[MAXM];
int e, head[MAXN], pre[MAXN], record[MAXN], inq[MAXN];
int dis[MAXN];
void addEdge(int x, int y, int cap, int cost, int sp) {
    assert(x < MAXN && y < MAXN && e < MAXM);
    if (sp == 0) {
        edge[e].x = x, edge[e].y = y, edge[e].cap = cap, edge[e].cost = cost;
        edge[e].sp = 0, 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].sp = 0, edge[e].next = head[y], head[y] = e++;
    } else {
        edge[e].x = x, edge[e].y = y, edge[e].cap = cap, edge[e].cost = cost;
        edge[e].sp = sp, edge[e].next = head[x], head[x] = e++;
        edge[e].x = y, edge[e].y = x, edge[e].cap = cap, edge[e].cost = -cost;
        edge[e].sp = -sp, edge[e].next = head[y], head[y] = e++;
    }
}
int pass[MAXN];
int f(Node &e) {
    if (e.sp == 0)
        return e.cost;
    if (e.sp == 1)
        return e.cost * pass[e.x] * 2 + 1;
    if (e.sp == -1) {
        if (pass[e.y] == 0)
            return 0x3f3f3f3f;
        return -(e.cost * pass[e.y] * 2 + 1);
    }
    assert(false);
}
int mincost(int s, int t, int n) {
    int mncost = 0;
    int flow, totflow = 0, x, y;
    int INF = 0x3f3f3f3f;
    for (int i = 0; i < n; i++)
        pass[i] = 0;
    while (1) {
        for (int i = 0; i <= n; i++)
            dis[i] = INF;
        dis[s] = 0;
        deque<int> Q;
        Q.push_front(s);
        while (!Q.empty()) {
            x = Q.front(), Q.pop_front();
            inq[x] = 0;
            for (int i = head[x]; i != -1; i = edge[i].next) {
                y = edge[i].y;
                int ecost = f(edge[i]);
                if (edge[i].cap > 0 && dis[y] > dis[x] + ecost) {
                    dis[y] = dis[x] + ecost;
                    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] == INF)
            break;
        flow = INF;
        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];
            if (edge[ri].sp == 0)
                edge[ri].cap -= flow;
            if (edge[ri^1].sp == 0)
                edge[ri^1].cap += flow;
                
            if (edge[ri].sp == 1)
                pass[edge[ri].x] ++;
            if (edge[ri].sp == -1)
                pass[edge[ri].y] --;
        }
        totflow += flow;
        mncost += dis[t] * flow;
    }
    return mncost;
}
const int MAXD = 105;
int main() {
    int testcase, N, S[1024], E[1024];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &N);
        
        for (int i = 0; i < N; i++)
            scanf("%d %d", &S[i], &E[i]);
        
        e = 0;
        memset(head, -1, sizeof(head));
        
        int source = N + MAXD + 2, sink = N + MAXD + 3;
        for (int i = 0; i < N; i++) {
            addEdge(source, i, 1, 0, 0);
            for (int j = S[i]; j <= E[i]; j++)
                addEdge(i, N + j, 1, 0, 0);
        }
        
        for (int i = 1; i < MAXD; i++)
            addEdge(N + i, sink, 1, 1, 1);
        
        int ret = mincost(source, sink, sink + 1);
        printf("%d\n", ret);
    }
    return 0;
}

Version 4

既然思路明確，再努力觀察一下規則。

等著夢月弄出更高端的寫法，由於第一層的節點連接是一個區間，又因為邊 cost 都是單向往 sink 流去，回溯邊根本派不上用場，掃描線思路放進去找增廣路徑，速度有了突破性地進展。

根據區間的右端點排序，依序加入事件。每一次加入後往左掃描，當找到可以交換的日期時，把當時的工作抓出來擴充交換區間，擴充的區間只會往左端點增長。

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
#include <stdio.h> 
#include <algorithm>
#include <set>
using namespace std;
const int MAXN = 1024;
const int MAXD = 105;
struct Time {
    int st, ed;
    bool operator<(const Time &a) const {
        return ed < a.ed;
    }
} T[MAXN];
int main() {
    int testcase, N;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &N);
        for (int i = 0; i < N; i++)
            scanf("%d %d", &T[i].st, &T[i].ed);
            
        sort(T, T + N);
        int ret = 0;
        int from[MAXD], assign[MAXN];
        set<int> event[MAXD];
        for (int i = 0; i < N; i++) {
            int l = T[i].st, r = T[i].ed;
            for (int j = r; j >= l; j--)                        // argument path
                from[j] = i;
            
            int day = r;    // choose
            for (int j = r; j >= l; j--) {
                if (event[j].size() < event[day].size())
                    day = j;
                if (event[day].size() == 0)
                    break;
                for (set<int>::iterator it = event[j].begin();
                    it != event[j].end(); it++) {
                    if (T[*it].st < l) {
                        for (int k = l-1; k >= T[*it].st; k--)  // argument path
                            from[k] = *it;
                        l = T[*it].st;
                    }
                }
            }
            
            ret += event[day].size() * 2 + 1;
            while (true) {
                int u = from[day];
                int d = assign[u];
                event[day].insert(u), assign[u] = day;
                if (u == i) break;
                event[d].erase(u), day = d;
            }
        }
        
        printf("%d\n", ret);
    }
    return 0;
}
Read More +
解題區/解題區 - 其他題目

2015 Google Code Jam Round 1B

windows format to linux format 

1
$ awk '{ sub("\r$", ""); print }' out.txt > output.txt

題解

  • A. Counter Culture
  • B. Noisy Neighbors
  • C. Hiking Deer

［A. Counter Culture］

給定一個數字 N，要求藉由兩種操作從 1 變成 N，第一種操作將當前數字 x 變成 x + 1，第二種操作為 x 變成 reverse(x)，並且消除前導為零。求操作的最少次數。

由於 N 很大，搜索沒有搞頭，但關於反轉數字能理解到，當後半部恰好等於目標的前半部時，此時反轉最有利，根據貪心策略進行反轉操作，但要防止前導為 0。關於 x + 1 部分，主要是增加位數。

這時候來逆推吧！降位數 (1000 -> 999, 10000 -> 9999)、反轉貪心 (123654 -> 100321)、WTF 的情況 (19 -> 11 -> 10)。在 WTF 的情況中，反轉無效，怒降一個數字。

［B. Noisy Neighbors］

在 R x C 的網格上，每一格可以租給一個用戶，當用戶之間共享一個邊時，將會增加不滿意程度，求租給 K 名用戶，建築的不滿意程度最低為何。

考慮 K 小的時候，將網格黑白染色，必然只放置在黑色或白色網格上，此時不滿意程度皆為 0。當 K 多餘白色格子或黑色格子時，將會增加不滿意程度，每當增加一格，勢必會挑選相對的顏色 (填滿白色格子後，選黑色格子來填)，那麼每一次必須挑最少相鄰邊的格子。

為什麼一定會填滿其中一種顏色？假設最優解存在其中一種顏色未填滿，且存在這一格 x 附近沒有使用的格子，那麼必然存在將一個產生不滿意的格子移動到 x 會是一個更優解。不斷地迭代下去，就是貪心的來源！

［C. Hiking Deer］

跟蹤狂 H 在一個圓從 0 出發繞一圈，H 很討厭人群，因此盡可能不與其他人碰面，H 的能力可以跟蹤在任何人身後。現在知道一群人會不斷地繞著這個圓，並且分別以各自的速度、當前位置，全部人都按著順時針方式繞行，不存在兩個人在相同地點以相同速度。現在從 time = 0 開始，請問 H 至少會發生幾次碰面。

由於是一個環狀，又要考慮繞行的區間最少人數，朝著掃描線思路邁進！保證答案 (碰面次數) 不超過總人數 N，一開始瞬間移動到最快抵達終點的人身上，只會碰到 N - 1 個人！

根據抵達終點的時間排序，維護當前需要的碰面次數 e，假設尾隨編號 i 的人，需要碰面 e 個人！經過掃描一些人後，又遇到 i，表示 i 又繞了一圈，那麼碰面次數 e = e + 1，讓尾隨後面的點時，都會遇到那該死的 i！

A code

GCJ20151B - Counter Culture
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
#include <stdio.h>
#include <string.h>
long long reverseNumber(long long x) {
    static char buf[32];
    sprintf(buf, "%lld", x);
    
    long long y = 0;
    for (int i = strlen(buf) - 1; i >= 0; i--)
        y = y * 10 + buf[i] - '0';
    return y;
}
long long f(long long n) {
    if (n < 10)
        return n;
    long long half = 1;
    while (half * half <= n)	
        half *= 10;
    if (n % half == 0)	// 1000 -> 999, 10000 -> 9999
        return 1 + f(n - 1);
    else {				
        long long v = reverseNumber(n - n%half + 1);
        if (v != n - n%half + 1)	// 123654 -> 100321, subtract & reverse
            return n%half + f(v);
        else						// 19 -> 11, but 11 is palindrome, without reverse -> 10
            return n%half + f(v-1);
    }
}
int main() {
    int testcase, cases = 0;
    long long n;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%lld", &n);
        printf("Case #%d: %lld\n", ++cases, f(n));
    }
    return 0;
}

B code

GCJ20151B - Noisy Neighbors
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
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
int main() {
    int testcase, cases = 0;
    int N, M, K;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d %d", &N, &M, &K);
        
        vector<int> B, W;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                int adj = 0;
                for (int k = 0; k < 4; k++) {
                    int x = i + dx[k], y = j + dy[k];
                    if (x >= 0 && y >= 0 && x < N && y < M)
                        adj++;
                }
                if ((i+j) %2 == 0)
                    B.push_back(adj), W.push_back(0);
                else
                    B.push_back(0), W.push_back(adj);
            }
        }
        
        sort(B.begin(), B.end());
        sort(W.begin(), W.end());
        
        int cost1 = 0, cost2 = 0, ret = -1;
        for (int i = 0; i < K; i++) {
            cost1 += B[i];
            cost2 += W[i];
        }
        ret = min(cost1, cost2);
        printf("Case #%d: %d\n", ++cases, ret);
    }
    return 0;
}

C code

GCJ20151B - Hiking Deer
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
#include <stdio.h>
#include <set>
#include <algorithm>
using namespace std;
const int MAXN = 524288;
int N, pass[MAXN];
struct Node {
    long long arrive_time, v;
    int id;
    Node(long long a = 0, int b = 0, long long c = 0):
        arrive_time(a), id(b), v(c) {}
    bool operator<(const Node &a) const {
        if (arrive_time != a.arrive_time)
            return arrive_time < a.arrive_time;
        return v < a.v;
    }
};
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &N);
        
        set<Node> pQ;
        int id = 0;
        long long D, H, M;
        for (int i = 0; i < N; i++) {
            scanf("%lld %lld %lld", &D, &H, &M);
            for (int j = 0; j < H; j++) {
                long long arrive_time = (360 - D) * (M + j);
                pQ.insert(Node(arrive_time, id, M + j));
                pass[id] = 0, id++;
            }
        }
        
        int ret = id, encounter = id;
        
        for (; encounter <= 2 * id; ) {
            Node u = *pQ.begin(); 			// extract minimum
            
            ret = min(ret, encounter);
            
            if (pass[u.id])
                encounter++;
            else
                encounter--;
            pass[u.id] = 1;
            
            pQ.erase(pQ.begin());
            pQ.insert(Node(u.arrive_time + u.v * 360, u.id, u.v));
        }
        
        printf("Case #%d: %d\n", ++cases, ret);
    }
    return 0;
}
Read More +
解題區/解題區 - 其他題目

2015 Google Code Jam Round 1A

\感謝諸神們替蒟蒻翻譯 GCJ 題目，巨人們/，看完第一題就過了一個小時。

windows format to linux format 

1
$ awk '{ sub("\r$", ""); print }' out.txt > output.txt

題解

  • A. Mushroom Monster
  • B. Haircut
  • C. Logging

［A. Mushroom Monster］O(N)

坑爹的蘑菇蘑菇，友人 A 會偷偷增加盤子上的蘑菇，系統每十秒會記錄盤子上蘑菇數量，也就是說給定的序列是系統紀錄盤子上蘑菇的情況，而不是友人 A 放入的蘑菇。接著少兩策略的最少吃掉數量

吃蘑菇策略一，可以在任何時刻吃掉任何數量，策略二，在任何時刻都以某個速度吃蘑菇每秒 f 個，當盤子空的時候，停止餵食。貪心策略，策略一考慮友人 A 盡可能不加蘑菇，策略二考慮友人 A 盡可能讓盤子空，在最後一個時刻 (系統紀錄前) 才放入蘑菇。

［B. Haircut］O(N log N)

理髮師 i 剪一個人需要 Mi 秒，客人 j 呈現 queue 的訪問方式，當有理髮師閒置時，將客人 j 會排入理髮程序。在同一時刻，若存在多名理髮師閒置，編號小的客人優先選擇編號小的理髮師進行流程。請問當所在位置為 N 時，會被指派給哪位理髮師。

二分自己剪髮時間，利算 sum += floor(time / Mi) + 1，存在 sum >= N 時，表示理髮廳已經解決 sum 個人，並且已經理超過自己。找到最小的時間後，循序找一下適合的理髮師。presum += floor(time / Mi) + (time % Mi != 0)，找到前一個時刻 time - 1 結束瞬間完成的人數，隨後貪心找 time % Mi = 0 分配給 presum + 1 ~ N。

［C. Logging］O(2^N * N log N) -> O(N^2 log N)

松鼠在樹 i 上，請問要砍掉幾棵樹，才能讓自己的樹 i 位於森林邊緣。

最簡單的思路，使用的點集，做一次凸包，查找位於邊上的可能情況，需要凸包算法、線段上判定、bitmask，應付小測資專用。O(2^N * N log N)

接著考慮要砍點使得點 i 在凸包邊緣，那麼必然找到一條線通過點 i，其中一側具有最少的點數。因此對於每一個點 i 當作中心，對其他 N - 1 個點進行極角排序，掃描線算法找半平面 (180 度) 內最少的點數。O(N^2 log N)。

A code

GCJ20151A - Mushroom Monster
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
// Fucking English
#include <stdio.h> 
#include <algorithm>
using namespace std;
int main() {
    int testcase, n, cases = 0;
    long long A[1024];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        
        for (int i = 0; i < n; i++)
            scanf("%lld", &A[i]);
        
        long long retA = 0, retB = 0, mx = 0;
        for (int i = 1; i < n; i++) {
            if (A[i-1] - A[i] > 0) {
                retA += A[i-1] - A[i];
                mx = max(mx, A[i-1] - A[i]);
            }
        }
        for (int i = 0; i < n - 1; i++) {
            if (A[i] > mx)
                retB += mx;
            else
                retB += A[i];
        }
        
        printf("Case #%d: %lld %lld\n", ++cases, retA, retB);
    }
    return 0;
}
/*
4
4
10 5 15 5
2
100 100
8
81 81 81 81 81 81 81 0
6
23 90 40 0 100 9
*/

B code

GCJ20151A - Haircut
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
#include <stdio.h>
int main() {
    int testcase, cases = 0;
    int N, B;
    long long M[1024];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &B, &N);
        for (int i = 0; i < B; i++)
            scanf("%lld", &M[i]);
        
        long long l = 0, r = 100000LL * N, mid, time = 0;
        while (l <= r) {
            mid = (l + r)/2;
            long long cnt = 0;
            for (int i = 0; i < B; i++)
                cnt += mid / M[i] + 1;
            if (cnt >= N)
                r = mid - 1, time = mid;
            else
                l = mid + 1;
        }
        
        long long cnt = 0;
        int id = 0;
        
        for (int i = 0; i < B; i++)
            cnt += time / M[i] +(time % M[i] !=0);
        
        cnt = N - cnt;
//		printf("%lld %lld\n", cnt, time);
        for (int i = 0; i < B; i++) {
            if (time % M[i] == 0) {
                cnt--;
                if (cnt == 0)
                    id = i;
            }
        }
        printf("Case #%d: %d\n", ++cases, id + 1);
    }
    return 0;
}

C code

small

GCJ20151A - Logging
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
#include <stdio.h> 
#include <math.h>
#include <algorithm>
#include <set>
#include <assert.h>
#include <vector>
using namespace std;
#define eps 1e-8
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}	
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    Pt operator*(const double a) const {
        return Pt(x * a, y * a);
    }
    bool operator==(const Pt &a) const {
    	return fabs(x - a.x) < eps && fabs(y - a.y) < eps;
    }
    bool operator<(const Pt &a) const {
        if (fabs(x - a.x) > eps)
            return x < a.x;
        if (fabs(y - a.y) > eps)
            return y < a.y;
        return false;
    }
    double length() {
        return hypot(x, y);
    }
    void read() {
        scanf("%lf %lf", &x, &y);
    }
};
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
double cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
int between(Pt a, Pt b, Pt c) {
    return dot(c - a, b - a) >= -eps && dot(c - b, a - b) >= -eps;
}
int onSeg(Pt a, Pt b, Pt c) {
    return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
struct Seg {
    Pt s, e;
    double angle;
    int label;
    Seg(Pt a = Pt(), Pt b = Pt(), int l=0):s(a), e(b), label(l) {
//		angle = atan2(e.y - s.y, e.x - s.x);
    }
    bool operator<(const Seg &other) const {
        if (fabs(angle - other.angle) > eps)
            return angle > other.angle;
        if (cross(other.s, other.e, s) > -eps)
            return true;
        return false;
    }
    bool operator!=(const Seg &other) const {
        return !((s == other.s && e == other.e) || (e == other.s && s == other.e));
    }
};
Pt getIntersect(Seg a, Seg b) {
    Pt u = a.s - b.s;
    double t = cross2(b.e - b.s, u)/cross2(a.e - a.s, b.e - b.s);
    return a.s + (a.e - a.s) * t;
}
double getAngle(Pt va, Pt vb) { // segment, not vector
    return acos(dot(va, vb) / va.length() / vb.length());
}
Pt rotateRadian(Pt a, double radian) {
    double x, y;
    x = a.x * cos(radian) - a.y * sin(radian);
    y = a.x * sin(radian) + a.y * cos(radian);
    return Pt(x, y);
}
const double pi = acos(-1);
int cmpZero(double v) {
    if (fabs(v) > eps) return v > 0 ? 1 : -1;
    return 0;
}
int monotone(int n, Pt p[], Pt ch[]) {
    sort(p, p+n);
    int i, m = 0, t;
    for(i = 0; i < n; i++) {
        while(m >= 2 && cross(ch[m-2], ch[m-1], p[i]) <= 0)
            m--;
        ch[m++] = p[i];
    }
    for(i = n-1, t = m+1; i >= 0; i--) {
        while(m >= t && cross(ch[m-2], ch[m-1], p[i]) <= 0)
            m--;
        ch[m++] = p[i];
    }
    return m-1;
}
int main() {
    int testcase, cases = 0;
    int n;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        Pt P[1024];
        for (int i = 0; i < n; i++)
            scanf("%lf %lf", &P[i].x, &P[i].y);
        
        int ret[16] = {};
        for (int i = 0; i < n; i++)
            ret[i] = n;
        for (int i = 0; i < (1<<n); i++) {
            int m = 0, cnt = 0;
            Pt a[32], ch[32];
            for (int j = 0; j < n; j++) {
                if ((i>>j)&1)
                    a[m++] = P[j];
            }
            
            int cn = monotone(m, a, ch);
            for (int p = 0; p < n; p++) {
                if ((i>>p)&1)
                for (int j = 0, k = cn-1; j < cn; k = j++) {
                    if (onSeg(ch[j], ch[k], P[p])) {
                        ret[p] = min(ret[p], n - m);
                    }
                }
            }
        }
        printf("Case #%d:\n", ++cases);
        for (int i = 0; i < n; i++)
            printf("%d\n", ret[i]);
    }
    return 0;
}

large

2015/05/15 修正極角排序誤差

Tricky Test Case

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
1
30
0 0
-971645 838743
748096 -988877
-652232 -993753
737167 -838743
-48 27
706721 -885828
606199 854425
659001 -993753
898961 885828
-659001 885828
748096 -973880
21 -13
-748096 606199
-732894 991850
13 -12
659001 -737167
-32 -32
737167 -748096
650983 -971645
650983 -732894
854425 -606199
-606199 885828
916399 -988877
652232 -838743
-606199 988877
-620105 -652232
-748096 -737167
24 -23
916399 854425

Output

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
Case #1:
9
0
1
0
3
7
4
2
0
0
2
2
8
1
0
9
7
7
4
3
8
1
2
0
7
0
2
0
9
0

盡可能地少用 atan2()，使用外積的方式進行極角排序。

GCJ20151A - Logging[fast]
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
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
#define eps 1e-6
#define MAXN 131072
struct Pt {
    double x, y;
    int label;
    Pt(double a = 0, double b = 0, int c = 0):
    x(a), y(b), label(c) {}
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    Pt operator*(const double a) const {
        return Pt(x * a, y * a);
    }
    bool operator<(const Pt &a) const {
        if (fabs(x - a.x) > eps)
            return x < a.x;
        if (fabs(y - a.y) > eps)
            return y < a.y;
        return false;
    }
};
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
double cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
int between(Pt a, Pt b, Pt c) {
    return dot(c - a, b - a) >= -eps && dot(c - b, a - b) >= -eps;
}
int onSeg(Pt a, Pt b, Pt c) {
    return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
Pt D[4096];
bool cmp(const Pt& p1, const Pt& p2)
{
    if (p1.y == 0 && p2.y == 0 && p1.x * p2.x <= 0) return p1.x > p2.x;
    if (p1.y == 0 && p1.x >= 0 && p2.y != 0) return true;
    if (p2.y == 0 && p2.x >= 0 && p1.y != 0) return false;
    if (p1.y * p2.y < 0) return p1.y > p2.y;
    double c = cross2(p1, p2);
    return c > 0 || c == 0 && fabs(p1.x) < fabs(p2.x);
}
int main() {
    int N, testcase, cases = 0;
    double x, y;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &N);
        for (int i = 0; i < N; i++) {
            scanf("%lf %lf", &x, &y);
            D[i] = Pt(x, y);
        }
        printf("Case #%d:\n", ++cases);
        
        if (N == 1) {
            puts("0");
            continue;
        }
        
        for (int i = 0; i < N; i++) {
            vector< Pt > A;
            for (int j = 0; j < N; j++) {
                if (i == j)
                    continue;
                Pt p = D[j] - D[i];
                A.push_back(p);
            }
            sort(A.begin(), A.end(), cmp);
            int M = (int)A.size();
            int l = 0, r = 0, cnt = 1;
            int ret = 0;
            for (l = 0; l < M; l++) {
                if (l == r)
                    r = (r+1)%M, cnt++;
                while (l != r && cross2(A[l], A[r]) >= 0) {
                    r = (r+1)%M, cnt++;
                }
                ret = max(ret, cnt);
                cnt--;
            }
            printf("%d\n", N - ret);
        }
    }
    return 0;
}
Read More +
解題區/解題區 - 其他題目

HDU 5097 - Page Rank

Problem

配合上一篇巨量資料的學習，利用馬可夫過程找到 Page Rank。

Sample Input

1
2
3
4
5
4
0111
0011
0001
0100

Sample Output

1
0.15 1.49 0.83 1.53

Solution

然而 Page Rank 計算主要分成兩種，一種是指派所有的 Page Rank 總合為 S，如果加起來不足 S，則把不足的部分平攤給所有節點，這麼一來計算誤差就可以被碾平，但這樣會會因為太多網頁，而導致單一 Rank 過小。

另外一種，則單純倚靠隨機的全局擴散，雖然會有計算誤差，持續做下去一樣會收斂。

為了加快速度，將公式的$1 - \beta$ 提出，沒有必要將一個稀疏矩陣變成稠密矩陣，如果每一個矩陣元素都加上$\frac{1 - \beta}{N}$ 會導致整個矩陣不存在非 0 的元素，而事實上 0 的元素是相當多的。這麼一來每次迭代的效率為$O(E)$，而非$O(N^{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
#include <stdio.h>
#include <math.h>
#include <vector>
#include <string.h>
using namespace std;
// Markov process, math
const int MAXN = 4096;
const int MAXIT = 9999;
class PageRank {
public:
    const double eps = 1e-10;
    vector<int> g[MAXN], invg[MAXN];
    vector<double> r;
    int N;
    double beta, S;
    void init(int n, double beta) {
        this->N = n;
        this->beta = beta;
        for (int i = 0; i < n; i++)
            g[i].clear(), invg[i].clear();
    }
    void addEdge(int u, int v) {
        g[u].push_back(v);
        invg[v].push_back(u);
    }
    bool isComplete(vector<double> &a, vector<double> &b) {
        double e = 0;
        for (int i = (int) a.size() - 1; i >= 0; i--) {
            e += (a[i] - b[i]) * (a[i] - b[i]);
        }
        return e < eps;
    }
    void compute() {
        vector<double> next_r(N, 0);
        r.resize(N, 1.0);
        
        for (int it = 0; it < MAXIT; it++) {
            for (int i = 0; i < N; i++) {
                double tmp = 0;
                for (int j = 0; j < invg[i].size(); j++) {
                    int x = invg[i][j];
                    tmp += r[x] / g[x].size();
                }
                next_r[i] = tmp * beta + (1.0 - beta);
            }
            if (isComplete(r, next_r)) {
                r = next_r;
                return ;
            }
            r = next_r;
        }
    }
} g;
char s[MAXN][MAXN];
int main() {
    const double beta = 0.85f;
    int N;
    while (scanf("%d", &N) == 1) {
        for (int i = 0; i < N; i++)
            scanf("%s", s[i]);
        
        g.init(N, beta);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (s[i][j] == '1') {
                    g.addEdge(i, j);
                }
            }
        }
        
        g.compute();
        
        for (int i = 0; i < N; i++) {
            printf("%.2lf%c", g.r[i], i == N - 1 ? '\n' : ' ');
        }
    }
    return 0;
}
Read More +
解題區/解題區 - 其他題目

2015 Facebook Hacker Cup Round 1

起床才發現，Facebook Hacker Cup Round 2 比賽不是比 24 小時，翻譯機的小夥伴醒了嗎？在這樣的情況下，只好自主宣告放棄，看題一直失敗，整個心情都壞了。關於 Round 2，根本沒看懂題目，就這麼結束了。

［2015 Facebook Hacker Cup Round 1］

＊Homework (10 points)

數學老師給一份質數作業，要求找到 [A, B] 之間的正整數，有多少不同質因數個數恰好等於 K 個，例如 12 = 2^2 * 3，則 f(12) = 2。寫一個程式來快速完成它。

A, B 小於等於 1000 萬，而詢問組數不超過 100 組，預估就算 O(n) 窮舉，速度來說仍然可以在時間內完成。無聊可以使用線性篩法，快速得到某個數字 x 必含的其中一個質因數來加速，f(x) = f(y) + 1, x = y * z, z power of prime nubmer。而區間查找可以針對 K 分開成數組，進行二分搜索。這樣寫太拚，有六分鐘的時間，暴力一點也無仿。

＊Autocomplete (25 points)

手機輸入單詞，會自動補上正在輸入單字的後綴，現在要求依序輸入單字，至少要敲入幾個字母，才能將所有單字完成。這題有點奇怪，照理來說要給定一個字典，接著開始鍵入，但這題是根據之前輸入的單詞，如果前綴相同就不能自動完成，怎麼補完的一點都不科學。

這題用內建 set<string>，可以使用 iterator it = map.lower_bound(word), it--; 來找到最有可能的前綴單詞，一定得輸入最大共同前綴長 +1，如果不想用內建，可以帶入 Trie 來完成，保證單詞總長不超過 100 萬，在某些題目 Trie 的速度跟泛用性相當高。

＊Winning at Sports (25 points)

在比賽中，勝利情況分成有、無壓力兩種方案，無壓力的情況是過程中，最後獲勝者的分數恆大於另一方，有壓力的情況是過程中，在另一方達到終盤分數前，最後獲勝者的分數不得大於另一方。現在給定終盤分數，請問兩種方案的比賽過程分別有多少種。

Dynamic programming 狀態 dp[a][b] 表示分別得分 a, b 的方法數，每次轉移 dp[a+1][b] += dp[a][b], dp[a][b+1] += dp[a][b] 特別小心條件範圍，分別對兩種方案做一次迭代。

＊Corporate Gifting (40 points)

每名員工都有一位上司，保證是樹狀結構，每名員工將要買禮物送給上司，禮物的花費為 $1, $2, …, $n，每個人都不想送出 $x 後，又從下屬中得到 $x 的禮物，請問該公司買禮物的總花費最小值為何？

樹狀最小帶權著色問題，套入樹形 Dp 的思路，定義狀態 dp[u][2] 表示以節點 u 當作 subtree root 的最佳解，其中 u 買 $?1,$?2 的兩種花費最小方案。合併時，窮舉 root 購入的價格，結合子樹的最小花費，防止同色即可。根據官方題解，使用的是 dp[u][log n]，可想而知數學推導得到最大購入不超過 $(log n)，但實際運作，我並沒有這麼做，而是看子樹最大著色數為何，再根據最大著色數進行窮舉。

這一題看到 N=200000 就要有點警惕，一般電腦預設 stack 大小，遞迴深度最多撐到 10 萬，呈現鏈狀很容易造成 stackoverflow，其一解決方案是編譯器調參數，其二 bfs 後的拓墣排序。

Read More +