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

ADA 2020 Fall P3. ADA Party

Algorithm Design and Analysis (NTU CSIE, Fall 2020)

Problem

給 $N$ 個堆，每個堆有 $a_i$ 個糖果，現在邀請 $K$ 個人，現在問有多少種挑選區間的方法，滿足扣掉最大堆和最小堆後，區間內的糖果總數可以被 $K$ 整除。

Sample Input

1
2
10 2
6 9 3 4 5 6 1 7 8 3

Sample Output

1
25

Solution

由於沒辦法參與課程，就測測自己產的測試資料，正確性有待確認。

分治處理可行解的組合，每一次剖半計算，統計跨區間的答案個數。

討論項目分別為

  • 最大值、最小值嚴格都在左側
  • 最大值、最小值嚴格都在右側
  • 最大值在左側、最小值在右側
  • 最大值在右側、最小值在左側

最後兩項會有交集部分，則扣除 在左側的最大最小值接等於右側的最大最小值。對於每一項回答，搭配單調運行的滑動窗口解決。

時間複雜度 $\mathcal{O}(n \log n)$、空間複雜度 $\mathcal{O}(n)$ 

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 <bits/stdc++.h>
using namespace std;
// Algorithm Design and Analysis (NTU CSIE, Fall 2020)
// Problem 3. ADA Party
const int MAXN = 500005;
const int32_t MIN = LONG_MIN;
const int32_t MAX = LONG_MAX;
int32_t a[MAXN];
int32_t lsum[MAXN], rsum[MAXN];
int32_t lmin[MAXN], lmax[MAXN];
int32_t rmin[MAXN], rmax[MAXN];
int cases = 0;
int mark[MAXN];
int counter[MAXN];
int n, k;
void inc(int32_t val) {
    val = (val%k+k)%k;
    if (mark[val] != cases)
        mark[val] = cases, counter[val] = 0;
    counter[val]++;
}
void dec(int32_t val) {
    val = (val%k+k)%k;
    if (mark[val] != cases)
        mark[val] = cases, counter[val] = 0;
    counter[val]--;
}
int get(int32_t val) {
    val = (val%k+k)%k;
    if (mark[val] != cases)
        mark[val] = cases, counter[val] = 0;
    return counter[val];
}
int64_t common(int l, int m, int r) {
    int64_t ret = 0;
    cases++;  // max and min is same on both end
    for (int i = m, j = m+1, jl = m+1; i >= l; i--) {
        while (j <= r && (rmax[j] <= lmax[i] && rmin[j] >= lmin[i])) {
            inc(rsum[j]-rmin[j]);
            j++;
        }
        while (jl < j && (rmin[jl] > lmin[i] || rmax[jl] < lmax[i])) {
            dec(rsum[jl]-rmin[jl]);
            jl++;
        }
        if (j > m+1 && lmin[i] == rmin[j-1] && lmax[i] == rmax[j-1])
            ret += get(k-(lsum[i]-lmax[i]));
    }
    return ret;
}
int64_t divide(int l, int r) {
    if (l >= r)
        return 0;
    int m = (l+r)/2;
    int32_t sum = 0;
    int32_t mn = MAX, mx = MIN;
    for (int i = m; i >= l; i--) {
        sum += a[i], mn = min(mn, a[i]), mx = max(mx, a[i]);
        if (sum >= k)	sum %= k;
        lsum[i] = sum, lmin[i] = mn, lmax[i] = mx;
    }
    sum = 0, mn = MAX, mx = MIN;
    for (int i = m+1; i <= r; i++) {
        sum += a[i], mn = min(mn, a[i]), mx = max(mx, a[i]);
        if (sum >= k)	sum %= k;
        rsum[i] = sum, rmin[i] = mn, rmax[i] = mx;
    }
    int64_t c1 = 0, c2 = 0, c3 = 0, c4 = 0;
    cases++; // min max on the left
    for (int i = m, j = m+1; i >= l; i--) {
        while (j <= r && lmin[i] < a[j] && a[j] < lmax[i]) {
            inc(rsum[j]);
            j++;
        }
        if (i < m)
            c1 += get(k-(lsum[i]-lmin[i]-lmax[i]));
    }
    cases++; // min max on the right
    for (int i = m+1, j = m; i <= r; i++) {
        while (j >= l && rmin[i] < a[j] && a[j] < rmax[i]) {
            inc(lsum[j]);
            j--;
        }
        if (i > m+1)
            c2 += get(k-(rsum[i]-rmin[i]-rmax[i]));
    } 
    cases++;  // min on the left, max on the right
    for (int i = m, j = m+1, jl = m+1; i >= l; i--) {
        while (j <= r && rmin[j] >= lmin[i]) {
            inc(rsum[j]-rmax[j]);
            j++;
        }
        while (jl < j && rmax[jl] < lmax[i]) {
            dec(rsum[jl]-rmax[jl]);
            jl++;
        }
        c3 += get(k-(lsum[i]-lmin[i]));
    }
    cases++; // min on the right, max on the left
    for (int i = m+1, j = m, jl = m; i <= r; i++) {
        while (j >= l && lmin[j] >= rmin[i]) {
            inc(lsum[j]-lmax[j]);
            j--;
        }
        while (jl > j && lmax[jl] < rmax[i]) {
            dec(lsum[jl]-lmax[jl]);
            jl--;
        }
        c4 += get(k-(rsum[i]-rmin[i]));
    }
    int64_t local = c1 + c2 + c3 + c4 - common(l, m, r);
    return local + divide(l, m) + divide(m+1, r);
}
int main() {
    while (scanf("%d %d", &n, &k) == 2) {
        for (int i = 0; i < n; i++)
            scanf("%d", &a[i]);
        memset(counter, 0, sizeof(counter[0])*k);
        int64_t ret = divide(0, n-1);
        printf("%lld\n", ret);
    }
    return 0;
}
Read More +
解題區/解題區 - 其他題目

ADA 2020 Fall P2. Bomb Game

Algorithm Design and Analysis (NTU CSIE, Fall 2020)

Problem

有數名玩家依序抵達遊戲，並且落在位置 $c_i$，並且具有防禦力 $d_i$，過程中會有炸彈發生於 $[l_i, r_i]$，對防禦力小於等於 $p_i$ 造成 $k_i$ 點傷害。

回報遊戲最後每一名玩家所受的傷害總額。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
10 10
P 3 5
A 2 8 15 5
P 7 10
A 4 10 5 3
A 1 9 10 7
P 6 20
P 5 1
A 4 9 17 2
A 1 2 20 4
P 9 5

Sample Output

1
2
3
4
5
12
9
0
2
0

Solution

由於沒辦法參與課程，就測測自己產的測試資料，正確性有待確認。

如果這一題目強制在線對答，則需要一個樹套樹在 $\mathcal{O}(\log^2 n)$ 內回答每一個結果，需要一個動態開區間的實作方法。

如果採用離線處理，則可以透過逆序處理來回答，可以透過二維空間的 BIT 結構來完成，這時候空間上會是另一個問題，即使使用懶惰標記，預期可能會達到 $\mathcal{O}(C \; D)$，通常是不允許的。

從分治算法切入，預想防禦能力高影響不受到攻擊力低的炸彈影響，無論時間與否都不受到影響。接下來，對防禦能力和攻擊力統稱力量。在分治的時候，對力量低的累計出答案，在合併階段受時間順序的影響才能回答。最後：

  1. 對力量從小到大排序
  2. 分治算法
    1. 對左區間和右區間按照時間由大到小排序
    2. 對於每一個左區間的詢問，插入所有滿足的右區間

時間複雜度 $\mathcal{O}(n \log^2 n)$、空間複雜度 $\mathcal{O}(n)$ 

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
#include <bits/stdc++.h>
using namespace std;
// Algorithm Design and Analysis (NTU CSIE, Fall 2020)
// Problem 2. Bomb Game
const int MAXN = 200005;
struct BIT {
    int64_t a[MAXN];
    int l[MAXN];
    int cases = 0;
    void add(int x, int val, int n) {
        while (x <= n) {
            if (l[x] != cases)
                l[x] = cases, a[x] = 0;
            a[x] += val, x += x&(-x);
        }
    }
    int64_t sum(int x) {
        int64_t ret = 0;
        while (x) {
            if (l[x] != cases)
                l[x] = cases, a[x] = 0;
            ret += a[x], x -= x&(-x);
        }
        return ret;
    }
    void reset(int n) {
        cases++;
    }
    void add(int l, int r, int k, int n) {
        add(l, k, n);
        add(r+1, -k, n);
    }
} bit;
int n;
struct PEvent {
    int c, d, i;
};
struct AEvent {
    int l, r, p, k;
};
struct Event {
    int type; // 'P' 0 or 'A' 1
    int time; // input order
    union {
        PEvent p;
        AEvent a;
    } data;
    int power() {
        if (type == 0)
            return data.p.d;
        else
            return data.a.p;
    }
    void println() {
        if (type == 0)
            printf("P %d %d\n", data.p.c, data.p.d);
        else
            printf("A %d %d %d %d\n", data.a.l, data.a.r, data.a.p, data.a.k);
    }
} events[MAXN];
static bool cmp_p(Event &a, Event &b) {
    int pa = a.power();
    int pb = b.power();
    if (pa != pb)
        return pa < pb;
    return a.time < b.time;
}
static bool cmp_t(Event &a, Event &b) {
    return a.time > b.time;
}
int ret[MAXN];
void resolve(int l, int m, int r) {
    sort(events+l, events+m+1, cmp_t);
    sort(events+m+1, events+r+1, cmp_t);
    //	printf("resolve %d %d =========\n", l, r);
    //	for (int i = l; i <= m; i++)
    //		events[i].println();
    //	puts("---");
    //	for (int i = m+1; i <= r; i++)
    //		events[i].println();
    bit.reset(n);
    int j = m+1;
    for (int i = l; i <= m; i++) {
        if (events[i].type)
            continue;
        int qtime = events[i].time;
        while (j <= r && events[j].time > qtime) {
            if (events[j].type) {
                bit.add(events[j].data.a.l,
                        events[j].data.a.r,
                        events[j].data.a.k,
                        n);
                //				printf("add %d %d %d %d\n", events[j].data.a.l,
                //						events[j].data.a.r,
                //						events[j].data.a.p,
                //						events[j].data.a.k);
            }
            j++;
        }
        //		printf("%d --- %d\n", events[i].data.p.i, bit.sum(events[i].data.p.c));
        ret[events[i].data.p.i] += bit.sum(events[i].data.p.c);
    }
}
void divide(int l, int r) {
    if (l >= r)
        return;
    int m = (l+r)/2;
    divide(l, m);
    divide(m+1, r);
    resolve(l, m, r);
}
int main() {
    int m;
    char s[2];
    scanf("%d %d", &n, &m);
    int id = 0;
    for (int i = 0; i < m; i++) {
        scanf("%s", s);
        events[i].time = i;
        if (s[0] == 'P') {
            events[i].type = 0;
            events[i].data.p.i = id++;
            scanf("%d %d",
                    &events[i].data.p.c,
                    &events[i].data.p.d);
        } else {
            events[i].type = 1;
            scanf("%d %d %d %d",
                    &events[i].data.a.l, 
                    &events[i].data.a.r,
                    &events[i].data.a.p,
                    &events[i].data.a.k);
        }
    }
    sort(events, events+m, cmp_p);
    divide(0, m-1);
    for (int i = 0; i < id; i++)	
        printf("%d\n", ret[i]);
    return 0;
}
Read More +
解題區/解題區 - 其他題目

關於高效大數除法的那些事

前情提要

從國小開始學起加減乘除，腦海裡計算加法比減法簡單，減法可以換成加法，乘法則可以換成數個加法。即使到了中國最強的利器——珠心算，我們學習這古老的快速運算時，也都採取這類方法，而除法最為複雜，需要去估算商，嘗試去扣完，再做細微調整。然而，當整數位數為 $N$ 時，加減法效能為 $N$ 基礎運算，而乘除法為 $N^2$ 次基礎運算，一次基礎運算通常定義在查表，例如背誦的九九乘法表，使得我們在借位和乘積運算達到非常快速。

這些方法在計算機發展後，硬體實作大致使用這些算法，直到了快速傅立葉 (FFT) 算法能在 $O(N \log N)$ 時間內完成旋積 (卷積) 計算，順利地解決了多項式乘法的問題，使得大數乘法能在 $O(N \log N)$ 時間內完成。

一開始我們知道乘法和除法都可以在 $O(N^2)$ 時間內完成，有了 FFT 之後，除法是不是也能跟乘法一樣在 $O(N \log N)$ 內完成？

大數除法

就目前研究來看，除法可以轉換成乘法運算，在數論的整數域中，若存在乘法反元素，除一個數相當於成一個數，而我們發展的計算機，有效運算為 32/64-bit，其超過的部分視為溢位 (overflow)，溢位則可視為模數。因此，早期 CPU 設計中，除法需要的運行次數比乘法多一些，編譯器會將除法轉換乘法運算 (企圖找到反元素)，來加速運算。現在，由於 intel 的黑魔法，導致幾乎一模一樣快而沒人注意到這些瑣事。

回過頭來，我們介紹一個藉由 FFT 達到的除法運算 $O(N \log N \log N)$ 的算法。而那多的 $O(\log N)$ 來自於牛頓迭代法。目標算出 $C = \lfloor A/B \rfloor$，轉換成 $C = \lfloor A \ast (1/B) \rfloor$，快速算出 $1/B$ 的值，採用牛頓迭代法。

額外要求整數長度 $n = \text{length}(A)$、$m = \text{length}(B)$，當計算 $1/B$ 時，要求精準度到小數點後 $n$ 位才行。

牛頓迭代法

目標求 $f(x) = 0$ 的一組解。

$$\begin{align} x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} \end{align}$$

不斷地迭代逼近找解。若有多組解，則依賴初始值 $x_0$ 決定優先找到哪一組解。

這部分也應用在快速開根號——反平方根快速演算法 Fast inverse square root

倒數計算

藉由下述定義，找到 $x = 1/B$

$$\begin{align} f(x) = \frac{1}{x} - B, \; f'(x) = -\frac{1}{x^2} \end{align}$$

接著推導牛頓迭代法的公式

$$\begin{align} x_{n+1} &= x_n - \frac{f(x_n)}{f'(x_n)} \\ &= x_n - \frac{\frac{1}{x} - B}{-\frac{1}{x^2}} = (2 - x_n B) x_n \end{align}$$

運行範例

當 $A = 7123456, \; B = 123$，計算倒數 $1/B = 1/123$，由於 $A$ 為 $n=7$ 位數，小數點後精準 7 位，意即迭代比較小數點後 7 位不再變動時停止。

以下描述皆以 十進制 (在程式運行時我們可能會偏向萬進制，甚至億進制來充分利用 32-bit 暫存器)

  • 決定 $x_0$ 是很重要的一步，這嚴重影響著迭代次數。
  • $x_0$ 拿 $B$ 的最高位數 1 進行大數除小數，得到 $x_0 = 0.01$
  • $x_1 = (2 - x_0 \ast B) \ast x_0 = 0.0077$
  • $x_2 = (2 - x_1 \ast B) \ast x_1 = 0.0081073$
  • $x_3 = (2 - x_2 \ast B) \ast x_2 = 0.00813001$
  • $x_4 = (2 - x_3 \ast B) \ast x_3 = 0.00813008$

接下來進行移位到整數部分，進行乘法後再移回去即可。

實作細節

精準度

使用浮點數實作的 FFT，需要小心精準度，網路上有些代碼利用合角公式取代建表。這類型的優化，在精準度不需要很高的時候提供較好的效能，卻無法提供精準的值，誤差修正成了一道難題。

牛頓迭代

由於有 FFT 造成的誤差，檢查收斂必須更加地保守，我們可能需要保留小數點下 $n+10$ 位，在收斂時檢查 $n+5$ 位確保收斂。通常收斂可以在 20 次左右完成，若發現迭代次數過多，有可能是第一個精準度造成的影響，盡可能使用內建函數得到的三角函數值。

加速優化

一般使用 IEEE-754 的浮點數格式，根據 FFT 的長度，要避開超過的震級，因此，在 Zerojudge b960 中，最多使用十萬進制進行加速。

誤差修正

儘管算出的商 $C=A \ast (1/B)$，得到的 $C$ 可能會差個 1，需要在後續乘法中檢驗。

參考題目/資料

b960 的亂碼

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
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
#include <bits/stdc++.h>
using namespace std;
template<typename T> class TOOL_FFT {
public:
    struct complex {
        T x, y;
        complex(T x = 0, T y = 0):
            x(x), y(y) {}
        complex operator+(const complex &A) {
            return complex(x+A.x,y+A.y);
        }
        complex operator-(const complex &A) {
            return complex(x-A.x,y-A.y);
        }
        complex operator*(const complex &A) {
            return complex(x*A.x-y*A.y,x*A.y+y*A.x);
        }
    };
    T PI;
    static const int MAXN = 1<<17;
    complex p[2][MAXN];
    int reversePos[MAXN];
    TOOL_FFT() {
        PI = acos(-1);
        preprocessing();
    }
    int NumberOfBitsNeeded(int PowerOfTwo) {
        for (int i = 0;; ++i) {
            if (PowerOfTwo & (1 << i)) {
                return i;
            }
        }
    }
    inline uint32_t FastReverseBits(uint32_t a, int NumBits) {
        a = ( ( a & 0x55555555U ) << 1 ) | ( ( a & 0xAAAAAAAAU ) >> 1 ) ;
        a = ( ( a & 0x33333333U ) << 2 ) | ( ( a & 0xCCCCCCCCU ) >> 2 ) ;
        a = ( ( a & 0x0F0F0F0FU ) << 4 ) | ( ( a & 0xF0F0F0F0U ) >> 4 ) ;
        a = ( ( a & 0x00FF00FFU ) << 8 ) | ( ( a & 0xFF00FF00U ) >> 8 ) ;
        a = ( ( a & 0x0000FFFFU ) << 16 ) | ( ( a & 0xFFFF0000U ) >> 16 ) ;
        return a >> (32 - NumBits);
    }
    
    void FFT(bool InverseTransform, complex In[], complex Out[], int n) {
        // simultaneous data copy and bit-reversal ordering into outputs
        int NumSamples = n;
        int NumBits = NumberOfBitsNeeded(NumSamples);
        for (int i = 0; i < NumSamples; ++i) 
            Out[reversePos[i]] = In[i];
            
        // the FFT process
        for (int i = 1; i <= NumBits; i++) {
            int BlockSize = 1<<i, BlockEnd = BlockSize>>1, BlockCnt = NumSamples/BlockSize;
            for (int j = 0; j < NumSamples; j += BlockSize) {
                complex *t = p[InverseTransform];
                int k = 0;
#define UNLOOP_SIZE 8
                for (; k+UNLOOP_SIZE < BlockEnd; ) {
#define UNLOOP { \
    complex a = (*t) * Out[k+j+BlockEnd]; \
    Out[k+j+BlockEnd] = Out[k+j] - a; \
    Out[k+j] = Out[k+j] + a;\
    k++, t += BlockCnt;\
}
#define UNLOOP4 {UNLOOP UNLOOP UNLOOP UNLOOP;}
#define UNLOOP8 {UNLOOP4 UNLOOP4;}
                    UNLOOP8;
                }
                for (; k < BlockEnd;)
                    UNLOOP;
            }
        }
        // normalize if inverse transform
        if (InverseTransform) {
            for (int i = 0; i < NumSamples; ++i) {
                Out[i] = Out[i].x / NumSamples;
            }
        }
    }
    void convolution(T *a, T *b, int n, T *c) {
        static complex s[MAXN], d1[MAXN], d2[MAXN], y[MAXN];
    	n = MAXN;
        for (int i = 0; i < n; ++i)
            s[i] = complex(a[i], 0);
        FFT(false, s, d1, n);
        s[0] = complex(b[0], 0);
        for (int i = 1; i < n; ++i)
            s[i] = complex(b[n - i], 0);
        FFT(false, s, d2, n);
        for (int i = 0; i < n; ++i)
            y[i] = d1[i] * d2[i];
        FFT(true, y, s, n);
        for (int i = 0; i < n; ++i)
            c[i] = s[i].x;
    }
    void preprocessing() {
        int n = MAXN;
        for (int i = 0; i < n; i ++) {
            p[0][i] = complex(cos(2*i*PI / n), sin(2*i*PI / n));
            p[1][i] = complex(p[0][i].x, -p[0][i].y);
        }
        
        int NumBits = NumberOfBitsNeeded(n);
        for (int i = 0; i < n; i++)
        	reversePos[i] = FastReverseBits(i, NumBits);
    }
};
TOOL_FFT<double> tool;
struct BigInt {
    long long *v;
    int size;
    static const int DIGITS = 5;
    static const int MAXN = 1<<17;
    static int compare(const BigInt a, const BigInt b) {
        for (int i = MAXN-1; i >= 0; i--) {
            if (a.v[i] < b.v[i])
                return -1;
            if (a.v[i] > b.v[i])
                return 1;
        }
        return 0;
    }
    void str2int(char *s, long long buf[]) {
        int n = strlen(s);
        size = (n+DIGITS-1) / DIGITS;
        int cnt = n%DIGITS == 0 ? DIGITS : n%DIGITS;
        int x = 0, pos = size-1;
        v = buf;
        for (int i = 0; i < n; i++) {
            x = x*10 + s[i] - '0';
            if (--cnt == 0) {
                cnt = DIGITS;
                v[pos--] = x, x = 0;
            }
        }
    }
    void println() {
        printf("%lld", v[size-1]);
        for (int pos = size-2; pos >= 0; pos--)
            printf("%05lld", v[pos]);
        puts("");
    }
    BigInt multiply(const BigInt &other, long long buf[]) const {
        int m = MAXN;
        static double na[MAXN], nb[MAXN];
        static double tmp[MAXN];
        memset(na+size, 0, sizeof(v[0])*(m-size));
        for (int i = 0; i < size; i++)
            na[i] = v[i];
        memset(nb+1, 0, sizeof(v[0])*(m-other.size));
        for (int i = 1, j = m-1; i < other.size; i++, j--)
            nb[j] = other.v[i];
        nb[0] = other.v[0];
        tool.convolution(na, nb, m, tmp);
        BigInt ret;
        ret.size = m;
        ret.v = buf;
        for (int i = 0; i < m; i++)
        	buf[i] = (long long) (tmp[i] + 1.5e-1);
        for (int i = 0; i < m; i++) {
        	if (buf[i] >= 100000)
        		buf[i+1] += buf[i]/100000, buf[i] %= 100000;
        }
        ret.reduce();
        return ret;
    }
    void reduce() {
        while (size > 1 && fabs(v[size-1]) < 5e-1)
            size--;
    }
    BigInt divide(const BigInt &other, long long buf[]) const {
        {
            int cmp = compare(*this, other);
            BigInt ret;
            ret.size = MAXN-1, ret.v = buf;
            if (cmp == 0) {
                memset(buf, 0, sizeof(buf[0])*MAXN);
                buf[0] = 1;
                ret.reduce();
                return ret;
            } else if (cmp < 0) {
                memset(buf, 0, sizeof(buf[0])*MAXN);
                buf[0] = 0;
                ret.reduce();
                return ret;
            }
        }
        // A / B = A * (1/B)
        // x' = (2 - x * B) * x
        int m = MAXN;
        static double na[MAXN], nb[MAXN];
        static double invB[MAXN], netB[MAXN], tmpB[MAXN];
        static long long bufB[MAXN];
        int PRECISION = size+10;
        memset(nb+1, 0, sizeof(v[0])*(m-other.size));
        for (int i = 1, j = m-1; i < other.size; i++, j--)
            nb[j] = other.v[i];
        nb[0] = other.v[0];
        
        memset(invB, 0, sizeof(invB[0])*m);
        {
            long long t = 100000, a = other.v[other.size-1];
            if (other.size-2 >= 0)
                t = t*100000, a = a*100000+other.v[other.size-2];
            for (int i = PRECISION-other.size; i >= 0; i--) {
                invB[i] = t/a;
                t = (t%a)*100000;
            }
        }
        for (int it = 0; it < 100; it++) {
            // netB = xi * B
            tool.convolution(invB, nb, m, netB);
            long long carry = 0;
            for (int i = 0; i <= PRECISION*2; i++) {
            	bufB[i] = carry + (long long) (netB[i] + 1.5e-1);
            	if (bufB[i] >= 100000)
            		carry = bufB[i]/100000, bufB[i] %= 100000;
            	else
            		carry = 0;
                bufB[i] = -bufB[i];
            }
            // tmpB = 2 - xi * B
            bufB[PRECISION] += 2;
            memset(tmpB, 0, sizeof(tmpB[0])*m);
            for (int i = 0; i <= PRECISION*2; i++) {
            	if (bufB[i] < 0)
            		bufB[i] += 100000, bufB[i+1]--;
            	if (i != 0)
            		tmpB[m-i] = bufB[i];
            	else
            		tmpB[i] = bufB[i];
            }
            // netB = tmpB * invB
            tool.convolution(invB, tmpB, m, netB);
            {
                long long carry = 0;
                memset(bufB, 0, sizeof(bufB[0])*m);
                for (int i = 0; i <= PRECISION*2; i++) {
                    bufB[i] = carry + (long long) (netB[i] + 1.5e-1);
                    if (bufB[i] >= 100000)
            			carry = bufB[i]/100000, bufB[i] %= 100000;
            		else
            			carry = 0;
                }
            }
            
            {
                int same = 1;
                for (int i = PRECISION; same && i >= 5; i--)
                    same &= ((long long) (invB[i]) == bufB[i+PRECISION]);
                if (same)
                    break;
            }
            memset(invB, 0, sizeof(invB[0])*m);
            for (int i = 0; i+PRECISION <= PRECISION*2; i++)
            	invB[i] = bufB[i+PRECISION];
        }
        
        memset(na+1, 0, sizeof(v[0])*(m-size));
        for (int i = 1, j = m-1; i < size; i++, j--)
            na[j] = v[i];
        na[0] = v[0];
        tool.convolution(invB, na, m, netB);
        
        BigInt ret;
        ret.size = m-1;
        ret.v = buf;
        long long carry = 0;
        for (int i = 0; i < m; i++) {
        	buf[i] = carry + (long long) (netB[i] + 1.5e-1);
        	if (buf[i] >= 100000)
        		carry = buf[i]/100000, buf[i] %= 100000;
        	else
        		carry = 0;
        }
        for (int i = 0; i+PRECISION < m; i++)
            buf[i] = buf[i+PRECISION];
        memset(buf+PRECISION, 0, sizeof(buf[0])*(m-PRECISION));
        {
        	memset(na, 0, sizeof(na[0])*m);
        	for (int i = 1, j = m-1; i < m-1; i++, j--)
                na[j] = buf[i];
            na[0] = buf[0];
            for (int i = 0; i < m; i++)
            	nb[i] = other.v[i];
    		tool.convolution(nb, na, m, netB);
    		long long carry = 0;
    		for (int i = 0; i < m; i++) {
    			bufB[i] = (carry + (long long) (netB[i] + 1e-1));
            	if (bufB[i] >= 100000)
            		carry = bufB[i]/100000, bufB[i] %= 100000;
            	else
            		carry = 0;
            }
            carry = 0;
            for (int i = 0; i < m; i++) {
                bufB[i] = v[i] - bufB[i] + carry;
                if (bufB[i] < 0)
            		bufB[i] += 100000, carry = -1;
            	else
            		carry = 0;
            }
            BigInt R;
            R.size = m-1, R.v = bufB;
            if (compare(other, R) <= 0) {
                buf[0]++;
                for (int i = 0; buf[i] >= 100000; i++)
                    buf[i+1]++, buf[i] -= 100000;
            }
        }
        ret.reduce();
        return ret;
    }
};
int main() {
    static char sa[1<<20], sb[1<<20];
    while (scanf("%s %s", sa, sb) == 2) {
        static long long da[1<<19], db[1<<19], dc[1<<19];
        
        BigInt a, b, c;
        a.str2int(sa, da);
        b.str2int(sb, db);
        c = a.divide(b, dc);
        c.println();
    }
    return 0;
}
Read More +
解題區/解題區 - 其他題目

2017 Google Code Jam Round QR

「在 24 小時內想不到解法，就註定這一生為處男」－《解題暴君》

感謝小夥伴們、茵可、妮可的提醒和翻譯，提醒要比賽，結果題目意思猜了一個下午 …

A. Oversized Pancake Flipper

有 $N$ 個煎餅排成一列，每個煎餅有正反兩面，分別以 + 和 - 表示，現在有一個超大的煎餅翻轉氣，一次可以翻轉恰好連續 $K$ 個煎餅的狀態，若一次不滿 $K$ 視為無效操作。給予起始盤面，請問至少要操作幾次才能使其全部都成為正面。

由邊界開始觀察，最左的正面一定不再被翻，如果翻了必然為多一次操作，不斷地推移下去，只有最左邊的反面要依序翻轉，貪心模擬即可。

B. Tidy Numbers

要找到一種特別的數字，這些數字滿足從高位到低位的每一位呈現非嚴格遞減，請問從數字 $1$ 判斷到 $N$ 最後一個滿足的數字為何。

最直觀的方案就 $N$ 開始倒退過去找第一個符合的解。為解決大測資，$N$ 大到不太可能窮舉，即便很容易出現 ???999999 的解，我們可以用更簡單的貪心算法找到這個小於等於 $N$ 的解。

  • 例如輸入為 423
  • 從最高位開始窮舉，第一位不能放 4，其原因在於貪心 444 已經大於 423，退而求其次 333 是可行的一組解
  • 接著再考慮下一位時，我們不必要求小於等於 2，因為前一次窮舉保證小於 423，直接從 9 開始嘗試 399 是否符合解 … 類推。

這樣的解法效能為 $O(m^2)$，由於位數很小，就可以偷懶地去寫它。

C. Bathroom Stalls

在公共澡堂中，有 $N$ 個位子排成一列，最左和最右有守衛。現在 $M$ 名使用者依照順序進入澡堂，每一個人會遠則離其他人盡可能遠的位置，意即往左和往右到第一個人的距離最小值最大化，往左距離為 $L_s$ 往右為 $R_s$，這樣的位置也許會有好幾個，這時候優先選擇 $\max(L_s, R_s)$ 最大的那一個 (也就是盡可能靠左側)。請問最後一個人的 $\max(L_s, R_s)$ 和 $\min(L_s, R_s)$ 分別為多少？

若使用純模擬，時間複雜度可能高達 $O(NM)$，大測資是無法在時間內通過的。仔細觀察到題目並未要求找到最後一個人的所在位置，在數學推敲上並不要求太高，那麼我們轉向繼續連續為空的區段分別有多少個。

  • 例如一開始長度為 $N=10$
  • 有一段長度為 10，第一個人必然會將這一個分成兩段 4 和 5
  • 下一個人則會把 5 再分成 2 和 2
  • 下一個人則會把 4 再分成 1 和 2

計算過程中，我們按照長度高到低依序挑出，便可以知道最終的結果。為了加速運算，需要紀錄某個長度有多少個，一次統計會使用相同挑選方案的人，來逼近最終的 $M$ 個人。時間複雜度 $O(\log N)$？

D. Fashion Show

在一個方型時尚展場中，我們可以放置 3 種不同的服裝，分別為 +, x, o 三種，其中 +, x 可以為展場增添 1 分，o 可以增添 2 分，我們希望按照下述的規則使得展場總分最高：

  • 對於同行或者同列的放置服裝，任兩個之中，至少要有一個為 +
  • 對於斜對角 45 度的放置服裝，任兩個之中，至少要有一個為 x

現在給予一個空的展場和一些已經放置服裝的位置，你只能升級 +, x 服裝為 o 和增加新的服裝在空位置上，使得分數最高，輸出其中一組解即可。

如果只看行列，通常我們可以轉換成二分匹配，其中 (行 i) -- (列 j) 表明了一種放置方案，而中間的匹配邊成為最終的放置選擇。現在多了斜對角，匹配成為最難處理的部份，

題目的規則可以轉換成，行列最多放置一個非 +，同理對角最多放置一個非 x。按照原先的匹配思路，如果放置 x，則相當於匹配某行某列。同理，放置 +，則相當於匹配某斜和某反斜。這裡我們發現如果同時匹配，則視為 o，其匹配數恰好符合題目要求的得分。

對於已經擺設上去的點，預先將其匹配，並且那些行、列、斜線及反斜的代表點則不再與其他節點匹配，最後，我們構造節點個數為 $6N$ 的二分匹配圖，運行匈牙利或者是最大流算法都可解決。

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
#include <bits/stdc++.h>
using namespace std;
int main() {
    int testcase, cases = 0, K;
    char s[1024];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%s %d", s, &K);
        int n = strlen(s);
        int ret = 0, valid = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] == '+')
                continue;
            if (i+K <= n) {
                ret++;
                for (int j = 0; j < K; j++) {
                    if (s[i+j] == '-')
                        s[i+j] = '+';
                    else
                        s[i+j] = '-';
                }
            }
        }
        valid = 1;
        for (int i = 0; i < n; i++)
            valid &= s[i] == '+';
        if (valid)
            printf("Case #%d: %d\n", ++cases, ret);
        else
            printf("Case #%d: IMPOSSIBLE\n", ++cases);
    }
    return 0;
}

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
#include <bits/stdc++.h>
using namespace std;
int main() {
    int testcase, cases = 0;
    uint64_t N;
    scanf("%d", &testcase);
    while (testcase--) {
        char s[1024];
        scanf("%s", s);
        sscanf(s, "%llu", &N);
        int n = strlen(s);
        uint64_t ret = 0;
        int begin_small = 0;
        for (int i = 0; i < n; i++) {
            int prev = ret%10;
            int st = begin_small ? 9 : (s[i]-'0');
            for (int j = st; j >= prev; j--) {
                uint64_t test = ret;
                for (int k = i; k < n; k++)
                    test = test*10 + j;
                if (test <= N) {
                    if (!begin_small && j != s[i]-'0')
                        begin_small = 1;
                    ret = ret*10 + j;
                    break;
                }
            }
        }
        printf("Case #%d: %llu\n", ++cases, ret);
    }
    return 0;
}

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
#include <bits/stdc++.h>
using namespace std;
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        long long n, m;
        scanf("%lld %lld", &n, &m);
        map<long long, long long> S;
        S[n] = 1;
        long long ret1 = -1, ret2 = -1;
        while (m) {
            pair<long long, long long> e = *S.rbegin();
            S.erase(e.first);
            if (e.second >= m) {
                ret1 = e.first/2, ret2 = (e.first-1)/2;
                break;
            }
            m -= e.second;
            if (e.first%2) {
                long long t = e.first/2;
                S[t] += 2LL*e.second;
            } else {
                long long t = e.first/2;
                S[t] += e.second;
                S[t-1] += e.second;
            }
        }
        printf("Case #%d: %lld %lld\n", ++cases, ret1, ret2);
    }
    return 0;
}

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
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
194
195
196
#include <bits/stdc++.h>
using namespace std;
const int MAXV = 40010;
const int MAXE = MAXV * 200 * 2;
const int INF = 1<<29;
typedef struct Edge {
    int v, cap, flow;
    Edge *next, *re;
} Edge;
class MaxFlow {
    public:
    Edge edge[MAXE], *adj[MAXV], *pre[MAXV], *arc[MAXV];
    int e, n, level[MAXV], lvCnt[MAXV], Q[MAXV];
    void Init(int x) {
        n = x, e = 0;
        for (int i = 0; i < n; ++i) adj[i] = NULL;
    }
    void Addedge(int x, int y, int flow){
        edge[e].v = y, edge[e].cap = flow, edge[e].next = adj[x];
        edge[e].re = &edge[e+1], adj[x] = &edge[e++];
        edge[e].v = x, edge[e].cap = 0, edge[e].next = adj[y];
        edge[e].re = &edge[e-1], adj[y] = &edge[e++];
    }
    void Bfs(int v){
        int front = 0, rear = 0, r = 0, dis = 0;
        for (int i = 0; i < n; ++i) level[i] = n, lvCnt[i] = 0;
        level[v] = 0, ++lvCnt[0];
        Q[rear++] = v;
        while (front != rear){
            if (front == r) ++dis, r = rear;
            v = Q[front++];
            for (Edge *i = adj[v]; i != NULL; i = i->next) {
                int t = i->v;
                if (level[t] == n) level[t] = dis, Q[rear++] = t, ++lvCnt[dis];
            }
        }
    }
    int Maxflow(int s, int t){
        int ret = 0, i, j;
        Bfs(t);
        for (i = 0; i < n; ++i) pre[i] = NULL, arc[i] = adj[i];
        for (i = 0; i < e; ++i) edge[i].flow = edge[i].cap;
        i = s;
        while (level[s] < n){
            while (arc[i] && (level[i] != level[arc[i]->v]+1 || !arc[i]->flow)) 
                arc[i] = arc[i]->next;
            if (arc[i]){
                j = arc[i]->v;
                pre[j] = arc[i];
                i = j;
                if (i == t){
                    int update = INF;
                    for (Edge *p = pre[t]; p != NULL; p = pre[p->re->v])
                        if (update > p->flow) update = p->flow;
                    ret += update;
                    for (Edge *p = pre[t]; p != NULL; p = pre[p->re->v])
                        p->flow -= update, p->re->flow += update;
                    i = s;
                }
            }
            else{
                int depth = n-1;
                for (Edge *p = adj[i]; p != NULL; p = p->next)
                    if (p->flow && depth > level[p->v]) depth = level[p->v];
                if (--lvCnt[level[i]] == 0) return ret;
                level[i] = depth+1;
                ++lvCnt[level[i]];
                arc[i] = adj[i];
                if (i != s) i = pre[i]->re->v;
            }
        }
        return ret;
    }
} g;
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        int n, m;
        scanf("%d %d", &n, &m);
        
        g.Init(6*n+5);
        static int mm[800][800];
        static int mmPos[800][800][2];
        int ret = 0;
        memset(mm, 0, sizeof(mm));
        int source = 6*n+1, sink = 6*n+2;
        int board[128][128] = {};
        int board_t[128][128] = {};
        char board_s[128][128] = {};
        int ban[800] = {};
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                mm[i][j+n] = 1;
                mm[(i+j)+2*n][(i-j+n-1)+4*n] = 1;
                mmPos[i][j+n][0] = i;
                mmPos[i][j+n][1] = j;
                mmPos[(i+j)+2*n][(i-j+n-1)+4*n][0] = i;
                mmPos[(i+j)+2*n][(i-j+n-1)+4*n][1] = j;
            }
        }
        for (int i = 0; i < m; i++) {
            char s[16];
            int x, y;
            scanf("%s %d %d", s, &x, &y);
            x--, y--;
            board_s[x][y] = s[0];
            if (s[0] == 'o') {
                ret += 2, board[x][y] = 2;
                ban[x] = 1, ban[y+n] = 1;
                ban[(x+y)+(2*n)] = 1;
                ban[(x-y+n-1)+4*n] = 1;
            } else if (s[0] == '+') {
                ret += 1, board[x][y] = 1;
                ban[(x+y)+(2*n)] = 1;
                ban[(x-y+n-1)+4*n] = 1;
//				printf("%d %d\n", x+y+2*n, x-y+n-1+4*n);
            } else if (s[0] == 'x') {
                ret += 1, board[x][y] = 1;
                ban[x] = 1, ban[y+n] = 1;
            }
        }
        memcpy(board_t, board, sizeof(board));
        
        for (int i = 0; i < n; i++)
            g.Addedge(source, i, 1);
        for (int i = 2*n; i < 4*n; i++)
            g.Addedge(source, i, 1);
        for (int i = n; i < 2*n; i++)
            g.Addedge(i, sink, 1);
        for (int i = 4*n; i < 6*n; i++)
            g.Addedge(i, sink, 1);
        
        for (int i = 0; i < n; i++) {
            for (int j = n; j < 2*n; j++) {
                if (ban[i] || ban[j] || !mm[i][j])
                    continue;
                g.Addedge(i, j, 1);
            }
        }
        for (int i = 2*n; i < 4*n-1; i++) {
            for (int j = 4*n; j < 6*n-1; j++) {
                if (ban[i] || ban[j] || !mm[i][j])
                    continue;
                g.Addedge(i, j, 1);
            }
        }
        
        int flow = g.Maxflow(source, sink);
        
        
        for (int i = 0; i < n; i++) {
            for (Edge *p = g.adj[i]; p != NULL; p = p->next) {
                if (p->v >= n && p->v < 2*n && p->flow == 0) {
                    board_t[mmPos[i][p->v][0]][mmPos[i][p->v][1]]++;
//					printf("---- %d %d\n", mmPos[i][p->v][0], mmPos[i][p->v][1]);
                    board_s[mmPos[i][p->v][0]][mmPos[i][p->v][1]] = 'x';
                }
            }
        }
        for (int i = 2*n; i < 4*n; i++) {
            for (Edge *p = g.adj[i]; p != NULL; p = p->next) {
                if (p->v >= 4*n && p->v < 6*n && p->flow == 0) {
                    board_t[mmPos[i][p->v][0]][mmPos[i][p->v][1]]++;
//					printf("---- %d %d\n", mmPos[i][p->v][0], mmPos[i][p->v][1]);
                    board_s[mmPos[i][p->v][0]][mmPos[i][p->v][1]] = '+';
                }
            }
        }
        
        struct DD {
            int x, y;
            char val;
            DD(int x, int y, char val): x(x), y(y), val(val) {}
        };
        vector<DD> V;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (board_t[i][j] != board[i][j]) {
                    if (board_t[i][j] == 2)
                        V.push_back(DD(i+1, j+1, 'o'));
//						printf("o %d %d\n", i+1, j+1);
                    else if (board_t[i][j] == 1)
                        V.push_back(DD(i+1, j+1, board_s[i][j]));
//						printf("%c %d %d\n", board_s[i][j], i+1, j+1);
                }
            }
        }
        printf("Case #%d: %d %d\n", ++cases, ret+flow, V.size());
        for (int i = 0; i < V.size(); i++)
            printf("%c %d %d\n", V[i].val, V[i].x, V[i].y);
    }
    return 0;
}
Read More +
解題區/解題區 - 其他題目

2017 Facebook Hacker Cup Round 1

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

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;
}
Read More +
解題區/解題區 - 其他題目

2017 Facebook Hacker Cup 資格賽

原本只是想推碩一學弟去寫，學弟邀著邀著，我這個老骨頭只好跟著寫

Facebook Hacker Cup 2017 Qualification Round

A. Progress Pie

給一個落在 $(0, 0)\; , (100, 100)$ 矩形內部的圓餅圖，並且從垂直十二點方向開始，順時針繞一圈 $P \%$ ，又額外給一座標，請問該點是黑色還是白色，並且保證任何一組詢問點，鄰近 $10^{-6}$ 都屬於相同顏色。

從最後一個條件來看，我們處理邊界條件的誤差是可以容忍的。由於輸入都是整數，完全在整數上操作的部分尚未想到，但我們可以透過內積外積得到詢問點是順時針轉了 $R, \; 0 \le R < 2 \pi$ ，只需要判斷 $R$ 是否小於等於 $P$ 即可。

十二點鐘的方向向量為 $\vec{v} = (0, 50)$ ，詢問點與圓心的向量為 $\vec{u} = (X-50, Y-50)$ ，計算這兩個向量的夾角 $\theta = \cos^{-1}(\frac{u \cdot v}{|u| |v|})$ ，這樣算出來的角度只會落在 $[0, \pi)$ ，接著透過外積決定順時針還是逆時針，補回來即可。

B. Lazy Loading

搬家公司的工人要搬運 $N$ 個重量不同的傢俱，主管要求每次搬運至少 50 磅，工人為了偷懶，每次只搬運一部份的傢俱，然而主管不會準確計算工人搬運的總重，只會問一次搬運的最大重量和個數，工人想藉由分配方法來增加工作天數，請問要怎麼符合需求達到最多搬運天數。

可想而知，我們只需要貪心計算即可，每次挑選最重的那一個，接著搭配當前最輕的來湊數，一超過 50 磅就當作一天的搬運方案，直到沒有物品。一開始排序好 $O(N \log N)$ ，接著只需要掃描一次 $O(N)$ 即可完成。

C. Fighting the Zombie

在 D&D 遊戲中，我們需要施放技能攻擊血量為 $H$ 的殭屍，施放採用擲骰子的方式，骰一個 $Y$ 面骰 $X$ 次得到的點數總和加上固定值 $Z$ ，請問一擊必殺的機率最高為何，由於盤面上有許多骰子可以挑選，請輸出機率最高的那個骰子的機率為何。

首先，我們必須先瞭解最基礎的六面骰，投擲 $X$ 總和的方法數怎麼計算，定義 $\text{dp}[i][j]$ 表示投擲 $i$ 次，點數總和為 $j$ 的方法數。我們得到

$$\begin{align*} dp[i][j] = \left\{\begin{matrix} 1 && i = 0\;, j = 0\\ dp[i-1][j-1] + dp[i-1][j-2] + \cdots + dp[i-1][j-6] && i \le j \\ 0 && \text{otherwise} \end{matrix}\right. \end{align*}$$

上述的遞迴考慮 $i-1$ 個骰子的總和方法數，再決定第 $i$ 個骰子擲出哪一種點數。然而，這種方法不適用此題計算機率，很容易發生 overflow，方法數的總和為 $Y^X$ ，所以一開始我們就採用機率的方式統計。

$$\begin{align*} dp[i][j] = \left\{\begin{matrix} 1 && i = 0\;, j = 0\\ (dp[i-1][j-1] + dp[i-1][j-2] + \cdots + dp[i-1][j-6])/6 && i \le j \\ 0 && \text{otherwise} \end{matrix}\right. \end{align*}$$

這樣的 DP 計算消耗時間 $O(X^2 Y^2)$ ，加上滑動窗口統計總和則可以落在 $O(X^2 Y)$ 。

比賽當下寫的，思路不是很清楚，變數命名和邏輯判斷會有點醜，沒有好好整理。

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
#include <bits/stdc++.h>
using namespace std;
int main() {
    const double eps = 1e-8;
    const double pi = acos(-1);
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        int P, X, Y;
        scanf("%d %d %d", &P, &X, &Y);
        int ret = 0;
        
        if (X == 50 && Y == 50) {
            ret = 1;
        } else if (hypot(X-50, Y-50) > 50) {
        } else if (P == 100) {
            ret = 1;
        } else if (P == 0) {
            
        } else {
            int vx = X-50, vy = Y-50;
            int tx = 0, ty = 50;
            double theta = acos((vx*tx+vy*ty)/hypot(vx, vy)/hypot(tx, ty));
            if (tx*vy - ty*vx > 0)
                theta = 2*pi-theta;
            double t = (double) P/100.0*2*pi;
            if (theta <= t)
                ret = 1;
        }
        printf("Case #%d: %s\n", ++cases, ret ? "black" : "white");
    }
    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
#include <bits/stdc++.h>
using namespace std;
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        int n;
        vector<int> A;
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            int x;
            scanf("%d", &x);
            A.push_back(x);
        }
        sort(A.begin(), A.end());
        int ret = 0;
        int r = n-1, l = 0;
        while (r >= l) {
            int need = ((50 + A[r]-1) / A[r]);
            if (l + need-1 > r)
                break;
            l += need-1, r--;
            ret++;
        }
        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
#include <bits/stdc++.h>
using namespace std;
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        int H, S;
        scanf("%d %d", &H, &S);
        vector< pair<int, int> > A;
        double ret = 0;
        for (int i = 0; i < S; i++) {
            char s[128];
            scanf("%s", s);
            int X = 0, Y = 0, Z = 0;
            for (int j = 0, x = 0, sign = 1, idx = 0; s[j]; j++) {
                if (isdigit(s[j]))
                    x = x * 10 + s[j] - '0';
                if (s[j+1] == '\0' || !isdigit(s[j])) {
                    x = x * sign;
                    if (idx == 0)
                        X = x;
                    else if (idx == 1)
                        Y = x;
                    else
                        Z = x;
                    if (s[j] == '-')
                        sign = -1;
                    else
                        sign = 1;
                    x = 0, idx++;
                }
            }
            int l = X+Z, r = X*Y+Z;
            static const int OFF = 1024;
            static double dp[2][OFF];
            for (int i = 0; i < OFF; i++)
                dp[0][i] = dp[1][i] = 0;
            dp[0][0] = 1;
            for (int i = 0; i < X; i++) {
                int p = i&1, q = i&1^1;
                for (int j = 0; j < OFF; j++)
                    dp[q][j] = 0;
                for (int j = 0; j < OFF; j++) {
                    if (dp[p][j] <= 0)	continue;
                    for (int k = 1; k <= Y; k++)
                        dp[q][j+k] += dp[p][j]*((double) 1.f/Y);
                }
            }
            double sum = 0;
            for (int j = 0; j <= X*Y; j++) {
                if (j+Z >= H)
                    sum += dp[(X-1)&1^1][j];
            }
            ret = max(ret, sum);
        }
        printf("Case #%d: %.6lf\n",++cases, ret);
    }
    return 0;
}
Read More +
解題區/解題區 - 其他題目

批改娘 10038. Fast Covering Problem

題目背景

終於把所有練習題都放上 Judge Girl，測資都已經確認過一遍，某 M 打算離開一陣子。「反正是個令人唾棄的助教吧 …」

題目描述

考試出題總很難讓所有人滿意，老師決定給予學生們選擇考試出題方向，但每一個人只能提出兩種意見，接著老師會出一套方案滿足每一位學生的其中一種意見。由於出一套題步驟繁瑣，把數個意見出在同一題非常困難，最後每一種意見將單獨被出成一道題。

由於助教們要負責出測資、檢驗測資正確與可行性，希望題目數量越少越好，否則助教會忙翻天。現在要找到最少題目來滿足所有學生的需求。

例如 :

  • 現在有 4 名學生的意見
  • 四名學生分別提案 $(0, 1), (100, 1), (100, 0), (100, 200)$
  • 如果選擇 ${ 0, 100 }$ 或者是 ${ 1, 100 }$ 都是最好的選擇，助教只需要完成 2 題的檢驗。相反地，如果 ${0, 100, 200 }$ 雖然可以滿足所有學生，但需要出成 3 道題目。

輸入格式

只有一組測資，每組第一行會有一個整數 $N$，表示有多少位學生，接下來會有 $N$ 行，每 $i$ 行上會有兩個整數 $A_i, B_i$ 表示第 $i$ 個學生的出題意見。

  • $0 < N \le 1000$
  • $0 \le A_i, \; B_i \le 10000$
  • 意見類型總數不超過 100 種

輸出格式

對於每一組測資輸出一行，表示最少要準備的方案數量能滿足所有學生。

範例輸入

1
2
3
4
5
4
0 1
100 1
100 0
100 200

範例輸出

1
2

提示

DLX

Solution

當年在 NCPC 搞不出來的 Problem I Christmas Gifts (NP-hard)，在賽後用 DLX 運行效果不錯，在啟發函數加上延遲標記更是屹立排名前數位已久。最近又因為平行把題目挖回來討論，在去年釣到大一學弟來解，便以飛快的速度擊破測資，最後達到加速 20x。再把當初需要跑 30 秒的測資來運行，現在只需要短短的 50ms。

原本要拿來出平行題目，看到這麼驚人的速度，想必就不要出題。

通用解法 DLX 加上啟發式函數就能解決最少重複覆蓋，然而在圖論的最少點集覆蓋問題中，性質又變得更加強烈。當不選某一個點時，必然與其相連的邊為了要覆蓋，另一端必然成為必選點。這時候搜索空間大幅度地下降。若在一般 DLX 算法中提及的最少可能的列中，窮舉某行來覆蓋一些列，那麼就很難看到搜索空間下降的性質。

因此，步驟簡單分成下列步驟：

  1. 將圖轉換成某行可以覆蓋哪幾列，轉換成 Dancing Links 的格式
  2. 找到可以覆蓋最多尚未覆蓋列最多的那一行
    1. 選擇這一行，並且移除這一行所有覆蓋列，遞迴窮舉。
    2. 移除這一行，選擇必選行，並嘗試移除等價行。

附錄：和交通大學謝旻錚(Min-Zheng Shieh) 教練的討論

在想確實能用 dancing links 來搞，還要搭配維護 degree order，不過這算法吳邦一老師是說 worst case 為 3 regular graph。
另外先前找過日本人 iwi 的論文，他也搞了個高級 VC solver 並做了測試，詳見論文 Branch-and-reduce exponential/FPT algorithms in practice: A case study of vertex cover, Takuya Akiba, Yoichi Iwata 

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
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <limits.h>
#define MAXNODE 100000
#define MAXCOL 5005
#define MAXN 5005
struct DancingNode {
    int left, right, up, down;
    int ch, rh;
} DL[MAXNODE];
struct HelperNode {
    int head, size, next, prev;
} HN[MAXNODE];
int help_head;
int s[MAXCOL];
int head, size, Ans, Dep;
int markStk[MAXNODE], markIdx = -1;
void Remove(int c) {
    for (int i = DL[c].down; i != c; i = DL[i].down) {
    	if (HN[DL[i].rh].head == i)
    		HN[DL[i].rh].head = DL[i].left;
    	HN[DL[i].rh].size--;
        DL[DL[i].right].left = DL[i].left;
        DL[DL[i].left].right = DL[i].right;
        s[DL[i].ch]--;
    }
}
void Resume(int c) {
    for (int i = DL[c].down; i != c; i = DL[i].down) {
    	if (HN[DL[i].rh].head == i)
    		HN[DL[i].rh].head = DL[i].right;
    	HN[DL[i].rh].size++;
        DL[DL[i].right].left = i;
        DL[DL[i].left].right = i;
        s[DL[i].ch]++;
    }
}
void Reduce(int i) {
    int t = DL[i].rh;
    HN[HN[t].next].prev = HN[t].prev;
    HN[HN[t].prev].next = HN[t].next;
    s[DL[i].ch]--;
    DL[DL[i].down].up = DL[i].up;
    DL[DL[i].up].down = DL[i].down;
    for (int k = DL[i].right; k != i; k = DL[k].right) {
        DL[DL[k].down].up = DL[k].up;
        DL[DL[k].up].down = DL[k].down;
        s[DL[k].ch]--;
    }
}
void Recover(int i) {
    int t = DL[i].rh;
    HN[HN[t].next].prev = t;
    HN[HN[t].prev].next = t;
    s[DL[i].ch]++;
    DL[DL[i].down].up = i;
    DL[DL[i].up].down = i;
    for (int k = DL[i].right; k != i; k = DL[k].right) {
        DL[DL[k].down].up = k;
        DL[DL[k].up].down = k;
        s[DL[k].ch]++;
    }
}
void Select(int i) {
    int s = DL[i].rh;
    HN[HN[s].next].prev = HN[s].prev;
    HN[HN[s].prev].next = HN[s].next;
    Remove(i);
    for (int j = DL[i].right; j != i; j = DL[j].right)
        Remove(j);
    Dep++;
}
void Cancel(int i) {
    int s = DL[i].rh;
    for (int j = DL[i].right; j != i; j = DL[j].right)
        Resume(j);
    Resume(i);    
    HN[HN[s].next].prev = s;
    HN[HN[s].prev].next = s;
    Dep--;
}
int Decision() {
    int has = 0;
    for (int i = DL[head].right; i != head; i = DL[i].right) {
        if (s[i] == 1) {
            Select(DL[i].down);
            markStk[++markIdx] = DL[i].down;
            has = 1;
        }
    }
    return has;
}
int Subset(int x, int y) {	// 0: x in y, 1: y in x 
    assert(DL[x].ch == DL[y].ch);
    int a = 0, b = 0;
    int i, j;
    for (i = DL[x].right, j = DL[y].right; i != x && j != y; ) {
        if (DL[i].ch == DL[j].ch)
            i = DL[i].right, j = DL[j].right;
        else if (DL[i].ch < DL[j].ch)
            i = DL[i].right, a = 1;
        else
            j = DL[j].right, b = 1;
        if (a && b)
            break;
    }
    if (i != x)    a = 1;
    if (j != y)    b = 1;
    return a || b ? (a - b) : 1;
}
int Duplicate() {
    int has = 0;
    for (int i = DL[head].right; i != head; i = DL[i].right) {
        for (int j = DL[i].down; j != i; j = DL[j].down) {
            for (int k = DL[j].down; k != j && k != i; k = DL[k].down) {
                int cmp = Subset(j, k);
                if (cmp == 0)
                    continue;
                if (cmp == 1) {
                	markStk[++markIdx] = j;
                	Select(j);
            	} else {
            		markStk[++markIdx] = k;
                	Select(k);
                }
                has = 1;
            }
        }
    }
    return has;
}
int H(int limit) {
    static int c, ret, i, j, time = 0;
    static int used[MAXCOL] = {};
    for (c = DL[head].right, ++time, ret = 0; c != head; c = DL[c].right) {
        if (used[c] == time)
        	continue;
    	ret ++, used[c] = time;
    	if (ret >= limit)	return ret;
        for (i = DL[c].down; i != c; i = DL[i].down) {
            for (j = DL[i].right; j != i; j = DL[j].right)
            	used[DL[j].ch] = time;
        }
    }
    return ret;
}
void DFS() {
    int hval = H(Ans - Dep);
    if (DL[head].right == head && Dep < Ans)
    	Ans = Dep;
    if (Dep + hval >= Ans)
        return ;
    int cover_max = -1, cover_idx = -1;
    for (int i = HN[help_head].next; i != help_head; i = HN[i].next) {
        if (HN[i].size > cover_max) {
            cover_max = HN[i].size;
            cover_idx = HN[i].head;
        }
    }
    
    Select(cover_idx);
    DFS();
    Cancel(cover_idx);
    
    Reduce(cover_idx);
    int markEsp = markIdx;
    while (!Decision() && !Duplicate());
    DFS();
    while (markIdx > markEsp)
        Cancel(markStk[markIdx--]);
    Recover(cover_idx);
}
int new_node(int up, int down, int left, int right) {
    DL[size].up = up, DL[size].down = down;
    DL[size].left = left, DL[size].right = right;
    DL[up].down = DL[down].up = DL[left].right = DL[right].left = size;
    return size++;
}
void new_row(int n, int Row[], int rh) {
    int r, row = -1, k;
    int h = size;
    for (int i = 0; i < n; i++) {
        r = Row[i];
        DL[size].ch = r, s[r]++;
        DL[size].rh = rh;
        if (row == -1) {
            row = new_node(DL[DL[r].ch].up, DL[r].ch, size, size);
        } else {
            k = new_node(DL[DL[r].ch].up, DL[r].ch, DL[row].left, row);
        }
    }
    HN[rh].size = n;
    HN[rh].head = h;
    HN[rh].next = HN[help_head].next;
    HN[rh].prev = help_head;
    HN[HN[help_head].next].prev = rh;
    HN[help_head].next = rh;
}
void init(int m) {
    size = 0;
    help_head = 0, HN[help_head].next = HN[help_head].prev = help_head;
    head = new_node(0, 0, 0, 0);
    int i;
    for (i = 1; i <= m; i++) {
        new_node(i, i, DL[head].left, head);
        DL[i].ch = i, s[i] = 0;
        DL[i].rh = 0;	// important pointer (fail pointer)
    }
}
int main() {
    int n;
    while (scanf("%d", &n) == 1 && n) {
    	int A[MAXN], B[MAXN];
        int toy[10005] = {}, R[MAXCOL];
        for (int i = 1; i <= n; i++) {
            scanf("%d %d", &A[i], &B[i]);
            toy[A[i]]++, toy[B[i]]++;
        }
        
        init(n);
        int run_id = 0;
        for (int i = 0; i <= 10000; i++) {
            int nt = 0;
            for (int j = 1; j <= n; j++) {
                if (A[j] == i || B[j] == i)
                    R[nt++] = j;
            }
            if (nt) {
                run_id++;
                new_row(nt, R, run_id);
            }
        }
        Ans = n;
        Dep = 0, markIdx = -1;
        Decision();
        DFS();
        printf("%d\n", Ans);
        fflush(stdout);
    }
    return 0;
}
Read More +
解題區/解題區 - 其他題目

2016 Google Code Jam Round 1A

A. The Last Word

每一字串 $S$，可視為一串操作，依序讀入一個字元 $C$，可以選擇把字元 $C$ 插入字串首或尾，請問字典順序最大為何？

類似 ZJ. 一串數字 之類的貪心方式，優先考慮最大字元在哪一個位置，抓取之後拆分兩串分開貪心合併，每一次由後往前找到第一個最大字典順序字元 $T$，$T$ 移到最前方，此時會將字串分成前半 $A$ 和後半 $B$，然而後半 $B$ 要排在 $T$ 字元之後，勢必只能按照順序丟入隊尾。因此 $\textit{MAXEXPR}(F) = T + \textit{MAXEXPR}(A) + B$。

B. Rank and File

給定一個 $N \times N$ 方格，每一行或列都是嚴格遞增，現在給定數個行、數個列的排列情況，請問缺漏的那一行或列的序列為何？

明顯地每一個數字都恰好出現偶數次，按照大小順序印出奇數次數字即可。

C. BFFs

給同學都有一位摯友，給定 $N$ 個人的好友資訊，現在要求盡可能多的人圍成一圈，並且每一個人其中一側是他們自己的摯友，請問圈最多幾個人。

明顯地，若不看方向性，每一個連通圖至多一個環。若一個連通圖式一個環，保證無法與其他方案合併在一起，因此用 $\mathcal{O}(N^2)$ 優先排除是環的解，在其中找最大圈即可。

接著考慮有觸手的水母圖，當水母大小恰好由兩個點構成時才會有解，因為三個點以上不符合題目要求的環。最後找到經過兩端點的最長觸手，這些點可以自我滿足，把所有最長觸手合併在一起可以構成一組特殊解。兩種方案取最大。

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
#include <bits/stdc++.h>
using namespace std;
string dfs(int n, string s) {
    if (n == 0)	return "";
    char mx = s[0];
    for (int i = 0; i < n; i++)
        mx = max(mx, s[i]);
    for (int i = n-1; i >= 0; i--) {
        if (s[i] == mx) {
            string mm = string(1, mx);
            return mm + dfs(i, s.substr(0, i)) + s.substr(i+1) ;
        }
    }
    return "";
}
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        char cs[1024];
        scanf("%s", cs);
        int n = strlen(cs);
        string v = dfs(n, cs);
        printf("Case #%d: %s\n", ++cases, v.c_str());
    }
    return 0;
}

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
#include <bits/stdc++.h>
using namespace std;
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        int n, m, x;
        map<int, int> R;
        scanf("%d", &n);
        m = 2*n-1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                scanf("%d", &x);
                R[x]++;
            }
        }
        printf("Case #%d:", ++cases);
        for (auto e : R) {
            if (e.second % 2 == 1)
                printf(" %d", e.first);
        }
        puts("");
    }
    return 0;
}

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
#include <bits/stdc++.h>
using namespace std;
int g[1024][1024];
vector<int> gg[1024];
int cc[1024];
int dfs(int u, int dep) {
    int ret = dep;
    for (auto v : gg[u]) {
        if (cc[v])	continue;
        int tmp = dfs(v, dep+1);
        ret = max(ret, tmp);
    }
    return ret;
}
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        int n, A[1024];
        
        memset(g, 0, sizeof(g));
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)
            gg[i].clear();
        for (int i = 1; i <= n; i++)
            scanf("%d", &A[i]), g[i][A[i]] = 1, gg[A[i]].push_back(i);
        int ret = 0;
        for (int i = 1; i <= n; i++) {
            int used[1024] = {};
            int u = i, cnt = 0;
            for (; used[u] == 0; u = A[u]) {
                used[u] = 1, cnt++;
            }
            if (u == i) 
                ret = max(ret, cnt);
        }
        memset(cc, 0, sizeof(cc));
        int cctot = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j)	continue;
                if (cc[i] || cc[j])	continue;
                if (g[i][j] == 0 || g[j][i] == 0)
                    continue;
                cc[i] = 1, cc[j] = 1;
                cctot += 2;
                cctot += dfs(i, 0) + dfs(j, 0);
            }
        }
        ret = max(ret, cctot);
        printf("Case #%d: %d\n", ++cases, ret);
    }
    return 0;
}
Read More +
解題區/解題區 - 其他題目

2016 Google Code Jam Round QR

一年一度的 GCJ 資格賽又開打了，這次的題目類型挺開放的，也就是有很多不同的解法可以通過。也許是因為都用了奇怪的方法解決。全寫完 Rank 400 名以內。

打完比賽完全沒心情寫水泥數學的作業證明。不！其實是不會寫。

A. Counting Sheep

睡覺前數羊，從一個基數 $N$ 開始，數 $N$, $2N$, $3N$, …, $?N$，直到 10 個位數都出現過，請問最後一個數的數 $?N$ 為何。

除了 $N = 0$ 的特殊情況外，直接模擬即可。最重要的是它不只有看個位數字，把每一位全看的狀況下，要湊滿 0-9 所有 digits 都出現過就不是難事。

B. Revenge of the Pancakes

現在 $N$ 個煎餅位於堆上，並且有分成兩個正反面狀態，每一次可以把煎餅從堆頂開始連續得拿出，並反轉序列放回堆中，同時把煎餅正反反轉，請問從一個開始序列轉移到全部皆為正面的操作次數最少為何？

一開始的策略是亂貪心一番，甚至題目看錯都能亂過小測資。必要任務一定是先把堆底那片煎餅翻成正的，這時一定堆頂為反，進行一次反轉讓堆底便成正的，為了讓堆頂為反，貪心策略盡可能讓堆頂一連續全部變成反。不斷地模擬此步驟即可。

C. Coin Jam

產生一個數字 $X$，$X$ 長度恰為 $N$，必須首尾皆為 1，只能由 0/1 構成。請產生數字 $X$，滿足在二進制、三進制 … 到十進制下皆為合成數。

這題莫名其妙指定 $N = 16, \; 32$，特殊的 $N$ 使得找到 $J$ 個 $X$ 並不難，更由於 $J$ 不大，各種解法都可以完成。從以往得概念，假設有一個數字 $A = 123123$，那麼保證不進位的情況下，找得到一組 $A = 123 \times 1001$，因此指定 $A = 1????1$，湊滿 $X = AA \cdots A$，不管在哪個進制下，勢必被 $A$ 整除。

D. Fractiles

詭異的數學碎形考古，給一個長度為 $K$ 的起始字串 $X$，$X$ 只由 $G$ 和 $L$ 構成。碎形迭代 $C$ 次，產生長度為 $K^C$ 的字串。現在雇用 $S$ 個學生，每個學生只能檢查一個位子，只要確定那一個位子有 $G$，那麼原始字串保證有 $G$。在限定學生數量下，請問要怎麼安排學生們的檢查工作。

由於長度為 $K$ 的起始字串有 $2^K$ 種，實際上只要剃除 $LL \cdots L$ 的字串。為了要在最少檢查位置下處理，必然要一個位置能否有 $G$，就能檢查原始字串的數個位置是否有 $G$。

窮舉只有 1 個 $G$ 個字串 $GLL...L$、$LGL...L$、… 等 $K$ 個，追蹤迭代 $C$ 次後，$K^C$ 長度下，每一個字串 $G$ 的出現位置。當 $C = 2$，可以讓位置 1, 2 的 $G$ 可以同時被檢查，同理位置 3, 4 的 $G$ 可以同時被檢查。當 $C = 3$ 時，位置 1, 2, 3 的 $G$ 可以同時被檢查。根據觀察，至少要 $\textit{ceil}(K/C)$ 個學生就能滿足需求。

第 $i$ 個學生要檢查的位置為 $1 + \sum_{0 \le j < C} (C(i-1)+(C-1-j))K^j$。

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
#include <bits/stdc++.h>
using namespace std;
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        long long n;
        scanf("%lld", &n);
        if (n == 0) {
            printf("Case #%d: INSOMNIA\n", ++cases);
            continue;
        }
        int has[128] = {}, ten = 10;
        long long on = n;
        while (1) {
            static char buf[32];
            sprintf(buf, "%lld", n);
            for (int i = 0; buf[i]; i++) {
                if (has[buf[i]] == 0) {
                    ten--, has[buf[i]] = 1;
                }
            }
            if (ten == 0)
                break;
            n += on;
        }
        printf("Case #%d: %lld\n", ++cases, n);
    }
    return 0;
}

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
#include <bits/stdc++.h>
using namespace std;
int main() {
    int testcase, cases = 0;
    char s[1024];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%s", s);
        int n = strlen(s), ret = 0;
        for (int i = n-1; i >= 0; i--) {
            if (s[i] == '+')	continue;
            int has = 0, j = 0;
            for (j = 0; j <= i; j++) {
                if (s[j] == '-')	break;
                has = 1;
            }
            if (has) {
                reverse(s, s+j);
                for (int k = 0; k < j; k++) {
                    if (s[k] == '-')
                        s[k] = '+';
                    else
                        s[k] = '-';
                }
            }
            ret += has;
            if (s[i] == '+')	continue;
            reverse(s, s+i+1);
            for (int k = 0; k < i+1; k++) {
                if (s[k] == '-')
                    s[k] = '+';
                else
                    s[k] = '-';
            }
            ret++;
        }
        printf("Case #%d: %d\n", ++cases, ret);
    }
    return 0;
}

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
#include <bits/stdc++.h>
using namespace std;
int main() {
    int testcase, cases;
    scanf("%d", &testcase);
    while (testcase--) {
        int N, J;
        scanf("%d %d", &N, &J);
        printf("Case #%d:\n", ++cases);
        set<long long> R;
        for (int i = 2; i < N && J; i++) {
            if (N%i)	continue;
            for (int j = 0; j < (1<<(i-2)) && J; j++) {
                int mask = (j<<1)|1|(1<<(i-1));
                long long v = 0;
                for (int k = 0; k < N/i; k++)
                    v = (v<<i) | mask;
                if (R.count(v))	continue;
                R.insert(v);
                for (int k = N-1; k >= 0; k--)
                    printf("%d", (v>>k)&1);
                for (int B = 2; B <= 10; B++) {
                    long long div = 0, nn = 0;
                    for (int k = i-1; k >= 0; k--)
                        div = div * B + ((mask>>k)&1);
                    for (int k = N-1; k >= 0; k--)
                        nn = nn * B + ((v>>k)&1);
//					assert(nn % div == 0 && nn != div);
                    printf(" %lld", div);
                }
                puts("");
                J--;
            }
        }
        assert(J == 0);
    }
    return 0;
}
/*
1
16 3
*/

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
#include <bits/stdc++.h>
using namespace std;
long long mpow(long long x, long long y) {
    long long ret = 1;
    while (y) {
        if (y&1)
            ret = ret * x;
        y >>= 1, x = x*x;
    }
    return ret;
}
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        long long K, C, S;
        scanf("%lld %lld %lld", &K, &C, &S);
        printf("Case #%d:", ++cases);
        
        int pos = 0;
        vector<unsigned long long> A;
//		puts("");
        for (int i = 0; i < ceil(1.f*K/C); i++) {
            int item = min(C, K - pos);
            unsigned long long x = 0;
            for (int j = C-1, k = 0; j >= 0 && k < item; j--, k++) {
//				printf("%d K^%d + ", pos + k, j);
                x += (pos + k) * mpow(K, j);
            }
            A.push_back(x);
//			puts("");
            pos += C;
            if (pos > K)	pos = K;
        }
        if (A.size() > S)
            puts(" IMPOSSIBLE");
        else {
            for (int i = 0; i < A.size(); i++)
                printf(" %llu", A[i]+1);
            puts("");
        }
    }
    return 0;
}
/*
5
4 4 5
*/
Read More +
解題區/解題區 - 其他題目

2016 Facebook Hacker Cup Round 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;
}
Read More +