2017 Google Code Jam Round QR

contents

  1. 1. A. Oversized Pancake Flipper
  2. 2. B. Tidy Numbers
  3. 3. C. Bathroom Stalls
  4. 4. D. Fashion Show
  5. 5. Solution
    1. 5.1. A
    2. 5.2. B
    3. 5.3. C
    4. 5.4. D

「在 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;
}