Google Code Jam 2019 资格轮题解

说起来很搞笑，4.7 凌晨 3 点我躺床上看群友聊到 GCJ 我才反应过来好像是资格赛，然后我随口问了一下什么时候这轮结束，特巨回了我一句：“你大概还剩…8 个小时？” 然后我掐指一算，早上 10 点截止，而我肯定写不来。幸好的是，A B 两个题的 Visible Set 就够晋级线 30 分了，躺床上把这两个题 Rush 出来我就睡了。第二天爬起来又想了想，把剩下两个题都写了。

这一轮其实四个题都很白给（比 Kickstart 简单一万倍），为什么写这一轮呢，主要是感觉这几题都还挺有意思的（难度也比去年低），加上好久没写题解了，练练手。其实官方是有题解的，就当我写了个翻译吧。

A. Foregone Solution

白给题 1 号。

题意

给定一个至少含有一个 $4$ 的数 $N$，求两个数 $A, B$ 都不包含 $4$ 且 $A+B=N$。

Test Set 1

由于 $N < 10^5$，暴力枚举 $A$ 然后检查一下 $A$ 和 $N-A$ 都包不包含 $4$ 就可以了。

Test Set 2

由于 $N<10^9$，枚举肯定不行了，我们可以考虑这么做：随机选一个在区间 $[1,N-1]$ 内的数 $A$，然后检查是否 $A$ 和 $N-A$ 都不包含 $4$ 就可以了。这样的做法是肯定没有问题的，但是复杂度够吗？

对于 $A$ 来说，我们考虑一下选出来这个数不包含 $4$ 的概率。这个概率很好求，由于每一位都是独立的，所以这个概率是 $(\frac{9}{10})^9 \approx0.387$。假如 $N-A$ 含有 $4$ 怎么办？我们可以考虑稍微的对 $A$ 做一下加减扰动一下，如果怎么扰动都含有 $4$，我们就重新随机。这样大概重复 100 次，我们最终的概率就是 $5.9\times10^{-42}$，几乎可以认为是 $0$ 了，这样就能得到一个解。

Analysis 里面讲了一个更严格的随机化证明，但是实际上这个东西有点杀鸡焉用牛刀了，而且明显有一个更 straightforward 的做法，我就不抄了。

Test Set 3

$N<10^{100}$，这么大个数字暴力还是随机化啊？

我相信绝大部分正常人都会想到这个解法：直接按位拆分，如 $7$ 分解成 $2+5$，顺序枚举每个位构造两个数就可以了，$\mathcal{O}(\text{len}(N))$。

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

## Full score, 6+10+1
T = int(input())

change = ['0', '0', '1', '1', '2', '2', '3', '2', '3', '3']
change_rev = [str(i - int(change[i])) for i in range(10)]

for kase in range(T):
    num = input()
    print(
        'Case #%d: %s %s' % (kase + 1, ''.join(change[int(it)] for it in num),
                             ''.join(change_rev[int(it)] for it in num)))

B. You Can Go Your Own Way

白给题 2 号。

题意

你从一个 $N\times N$ 大小的网格的起点 $(0,0)$ 开始走，只能向下（按题目说法，南，S）或者向右（东，E），走到 $(N,N)$。Lydia 已经走了这么一条路了，你不能重复她走过的任何一条路径，如她经过了路径 $(3,4)\to(3,5)$，你就不能走着一条路径，但经过相同的格子是允许的。给出 Lydia 的行走序列，请给出任何一种可行的方案。

Test Set 1

$2\le N\le 10$。直接枚举每一步怎么走然后模拟验证即可，$\mathcal{O}(N\cdot2^N)$。

Test Set 2

$2\le N \le 1000$。考虑从 $(0,0)$ 开始 DFS，直到走到 $(N,N)$ 位置，中间一旦遇到任何 Lydia 走过的路径就剪枝减掉。复杂度 $\mathcal{O}(N^2)$。

Test Set 3

至多十个测试点 $2\le N\le 50000$，剩余测试点 $1\le N\le 10000$。这个限制下肯定不能 DFS 了，我们来尝试其他做法。

如果你在纸上随便这么画一个网格，可能会得到一个观察：如果我沿对角线 $(0,0)-(N,N)$ 对 Lydia 走的路做一下对称，这样产生的新路径一定和 Lydia 走过的路没有任何重合。

我们来证明这个观察是对的。假设我们走了 $X$ 步右和 $Y$ 步下，那有一个直观的观察是，无论我们这几步右和下是怎么走的，我们最终来到的都是 $(X,Y)$ 这个点。也就是说，我们的位置和走法顺序无关，只和每个方向走了多少步有关。

那接下来我们来讨论两种情况：

• $X=Y$ 时，我们必定和 Lydia 相遇在同一个点，根据我们的策略，下一步我们走出的路径必定是 Lydia 所走路径的对称路径。这也就是说我们一定走出了和 Lydia 不同的路径。
• $X\ne Y$ 时，此时刚好会有$X_M=Y_L, Y_M=X_L$，我们所在的点也和 Lydia 所在的点沿对角线对称，我们更是不可能复用 Lydia 走过的路径。

所以这条对称的路径一定不会和 Lydia 的路径有重合的地方。那么我们直接构造这一条沿对角线对称的路线即可。实现上来说，就是 Lydia 如果走了 E 那我们就走 S，反之亦然。复杂度 $\mathcal{O}(N)$。

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

## Full score, 5+9+10
T = int(input())

for kase in range(T):
    input()
    R = input()
    ans = []
    for it in R:
        if it == 'S':
            ans.append('E')
        else:
            ans.append('S')

    print("Case #", end='')
    print(kase + 1, end='')
    print(':', ''.join(ans))

C. Cryptopangrams

这个题有点意思，但是还是比较基础的数论题。

题意

选择 26 个不大于 $N$ 的不同的质数，然后把 A-Z 从小到大一一对应到每一个质数上。然后我们对一个长度为 $L+1$ 的原文 $S$ 执行如下的加密操作：每相邻两位乘起来，得到一个 $L$ 长度的序列：$E_1=P_{S_1}\cdot P_{S_2}, \cdots, E_L=P_{S_L}\cdot P_{S_{L+1}}$。现在给定 $N, L, \{E_i\}$，求原文 $S$。$25\le L\le 100$，保证每个字母都在 $S$ 中出现过一次。

Test Set 1

$1\le N\le 10000$。由于限制很宽裕，质数的个数不超过 $10^4$ 个，埃筛一下然后每个数逐个测试一下，得到这个序列。

得到这个序列之后需要解密，解密过程看起来很复杂其实很简单，这是一个链式过程：由于我们知道 $E_1$ 是由前两个字母对应的数乘起来的，那么我们就找到这两个质数，分别测试一下就可以了：假定找到的两个解为 $P_1, P_2$，我们先使用 $p_1=P_1$ 去测试，这样我们就能得到 $p_2=E_2/p_1$，然后有了 $p_2$ 就能继续链式求下去。如果我们在这个过程中遇到了 $\gcd(p_i, E_{i+1})=1$ 的情况，那么代表这个链式操作出现了问题，$p_1$ 就不可能是 $P_1$，那答案就是 $P_2$，反之亦然。所以我们两次测试加上链式操作就可以解密出整个原文来。总复杂度为 $\mathcal{O}(NL+L)$。

Test Set 2

$1\le N\le10^{100}$。这个数实在是太大了，不可能挨个试所有质数。所以我们换个思路：求出所有可能的质数。

我们考虑一个简单的字符串： ABC，这样产生的序列为：$P_\text{A}\cdot P_\text{B},P_\text{B}\cdot P_\text{C}$。由于 $P_\text{A}, P_\text{B}$ 和 $P_\text{C}$ 是三个互不相同的质数，他们不会有任何的相同质因子，所以我们对上述两个数求一下最大公约数是多少？$P_\text{B}$！也就是说，我们只需要顺着求一遍相邻每两个数的质因子，然后就可以得到三个我们加密过程中用到的质数。排个序然后去一下重就可以了，拿一个 set 维护一下更方便。求最大公约数用辗转相除法就行，复杂度 $\mathcal{O}(\log N)$。

然而，上面的做法没有考虑到一个 case：ABA。这样得到的两个数 $E_1, E_2$ 是相等的，我们求不出任何一个质因子。这个问题的解决方法需要这样的一个观察：由于 26 个字母都会出现一次，也就是说，我们可以求出至少一个满足要求的质数。所以，我们并不一定需要求出 $P_\text{A}$ 或者 $P_{B}$，只要我们求出了其他一个质因子，最终都可以在链式的操作下求出这两个数。为了满足这个要求，我们只需要枚举每两个数，看看这两个数是否有一个公共的质因子，如果有的话，我们就可以顺着求出其他 25 个质数了，这个操作显然是 $\mathcal{O}(L^2)$ 的，由于 $25 \le L\le 100$，复杂度完全足够。

在求出所有质数之后，我们执行一遍测试集 1 的解密过程就行。总复杂度 $\mathcal{O}(L^2\log N+L)$。

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

## Full score but upsolved
from math import gcd

T = int(input())


def test(A, st, L):
    ret = [0] * L
    ret[0] = A[0] // st
    for idx in range(1, L):
        g = A[idx - 1] // ret[idx - 1]
        if gcd(A[idx - 1], g) == 1:
            return False, []
        ret[idx] = g

    return True, ret


for kase in range(T):
    N, L = map(int, input().split())
    A = list(map(int, input().split()))
    prime = set()
    ans = list()

    for i in range(L):
        for j in range(i + 1, L):
            g = gcd(A[i], A[j])
            if g != 1 and g != A[i]:
                prime.add(g)
                prime.add(A[i] // g)
                prime.add(A[j] // g)

    prime = list(sorted(prime))

    for it in prime:
        if A[0] % it == 0:
            ret, ans = test(A, it, L + 1)
            if ret:
                break

    print("Case #%d: %s" % (kase + 1, ''.join(
        chr(ord('A') + prime.index(it)) for it in ans)))

D. Dat Bae

这个题就非常好玩了，可以说是构造解中的典范。

题意

你有一个建在深山中的数据库，但是这个数据库最近出了问题。这个数据库是一个 $N$ 个 worker 组成的集群，编号为 $0\sim N-1$，你现在可以使用一个函数调用 TEST_STORE 发送一个长度为 $N$ 的 01 串给你的数据库，每台机器在收到消息后原样返回，也就是调用会给你返回完全相同的串。然而，有 $B$ 台 worker 坏了，这 $B$ 台机器并不会返回任何东西，也就是说，此时 TEST_STORE 调用只会给你返回 $N-B$ 长度的串。假设 $N=5,B=2$ 且坏掉的机器是 0 号和 3 号，那么调用会发生下面的结果：

• TEST_STORE 01101 返回 111。
• TEST_STORE 00110 返回 010。
• TEST_STORE 01010 返回 100。
• TEST_STORE 11010 也返回 100。

由于建在深山中的原因，TEST_STORE 调用的代价十分昂贵，所以你只能进行至多 $F$ 次调用。交互的向系统提出至多 $F$ 次询问，并给出坏了的 $B$ 台 worker 的编号。$2\le N\le 1024, 1\le B\le \min(15,N-1)$。

Test Set 1

$F=10$。我们考虑把这十次询问顺序从上到下排列起来，那这就是一个有 $N$ 列，10 行的 01 矩阵。现在我们不按行去看，而按列去考虑：假如某台机器 $a$ 坏了，那么在这个矩阵中，$a$ 列会全部消失。那现在问题就是，我们如何去定位这些消失的列。注意到每一列为一个 10 长度的 01 串，我们如果从上往下拿出某一列然后把它转置一下会得到什么？一个 10 长度的二进制数！由于共有 10 位，所以可以表示的最大数字是 $2^{10}=1024\ge N$！

所以，我们把 $0\sim N$ 用二进制编码出来，然后把它全部转置之后拼起来，并逐行询问，得到答案矩阵后再反向解码，这里面缺少的数就是那些坏掉的机器的编号，输出即可。

Test Set 2

$F=5$。此时 $2^5=32$，无法再像测试集 1 的做法去做了。不过，测试集 1 给到我们的提示就是如何设计编码协议，所以，我们来考虑如何在这个限制下设计编码协议。

注意到 $2^5=32>B=\min(15, N-1)$，也就是说，即使是连续的 $B$ 台机器损坏了，我们接收到的错误序号也在一次完整的编码范围内。这提示我们，可以分块：分成长度为 $32$ 的多个块，循环给每个块编码为 $0\sim31$，然后如上题一样的做法进行询问和解码。由于 $2^5>B$，如果连续的 $B$ 台设备损坏了，这一组损坏的机器只可能在某一块之内或者处于两块的交界，我们在顺着扫的过程中都能定位到这些缺失的编码，那么，对于更少的机器，我们自然也可以如此定位。与此同时，由于 $2^5>B$，连续损坏的机器不可能为完整的一块，所以我们能保证扫一遍定位出来的机器编号是唯一确定的。所以，这个做法是正确的。

而由于 $2^4=16>B$，我们甚至可以只使用 $4$ 次询问就得到答案！（见下面代码）为什么？我们假设 $B=16$，如果我们连续的 $B$ 台机器损坏了，那么可能损坏了完整的一块，这给我们定位带来了难度：考虑有四个循环编号的块 1 | 2 | 3 | 4，这四块是完全相同的。假设其中的某一块丢失，如 2 完整丢失了，那给我们返回的结果是 1 | 3 | 4。注意到问题了吗？这样的返回结果我们同样可以解释成 1 | 2 | 3 或者 2 | 3 | 4 等等。也就是说，如果 $2^4\ge B$ ，当完整的一块丢失的时候，我们完全无法定位丢失块的位置，我们也就无法唯一确定丢失编号了。而如果是大于关系，这样的要求就完全可以满足，所以，$F=4$ 的情况下，我们就可以得到答案。

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

// Full score but upsolved
#include <bits/stdc++.h>

using namespace std;

string numbers[]{
    "0000", "0001", "0010", "0011",
    "0100", "0101", "0110", "0111",
    "1000", "1001", "1010", "1011",
    "1100", "1101", "1110", "1111"};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int T;
    cin >> T;
    for (int kase = 1; kase <= T; kase++)
    {
        int N, B, F;
        cin >> N >> B >> F;
        vector<int> ans;
        vector<string> res(4);
        for (int i = 0; i < 4; i++)
        {
            stringstream ss;
            for (int p = 0; p < N; p++)
                ss << numbers[p % 16][i];

            cout << ss.str() << endl;
            cin >> res[i];
        }

        int cur = 0;

        for (int i = 0; i < N - B; i++)
        {
            stringstream ss;
            for (int p = 0; p < 4; p++)
                ss << res[p][i];

            int n = lower_bound(numbers, numbers + 16, ss.str()) - numbers;

            while (cur % 16 != n)
            {
                ans.push_back(cur);
                cur++;
            }
            cur++;
        }

        while (cur < N)
        {
            ans.push_back(cur);
            cur++;
        }

        assert(ans.size() == B);

        for (int i = 0; i < B; i++)
        {
            cout << ans[i];
            if (i == B - 1)
                cout << endl;
            else
                cout << ' ';
        }

        int t;
        cin >> t;
        assert(t == 1);
    }
}

说实话， Qualification Round 难度实在是过于简单了，整体水平就 CF Div 2 A~D 的水平，这也就导致了晋级了将近 2 万 7 千人，而 Round 1 要从这些人里面选 4500 人晋级下一轮，接下来可能白给的就是我了。

Anyway，省赛也快了，做点题回复一下手感，如果能晋级更好。不出意外的话，我们下一轮见。