目录

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,省赛也快了,做点题回复一下手感,如果能晋级更好。不出意外的话,我们下一轮见。