2017-04-09

2017 Google Code Jam Round QR

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

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

#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

#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

#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

#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;
}

Morris' Blog