- A1: Hello, World!
- A5: Spacedogs
- A7: Doubling Danny
- A9: Jumping Jimmy
- A12: Dicey Situation
- A13: Explodium!
- A15: Grand Hotel
- A16: Roshambolic
- D1: Gone to Seed
- D2: Hardcore Parkour
- D3: Wascally Wabbits
- D4: Task Genie
- D5: Snakes and Ladders
- D6: Two Quests
- D8: Garden Path
- D10: Paper Cut
- D11: Satisfaction
- D14: Prime Feast
GSA Ultra 2020
GSA Ultra 是英国的一家量化交易公司 GSA Capital 办的比赛。我之所以知道这个比赛是因为两个月前在学校邮箱收到了邮件。邮件内容非常神秘，点开链接后只看到标题和一个报名表，甚至不知道是什么样的比赛。抱着玩玩的心态报名了。
这个赛制其实还挺有意思的，但实在是有点内卷，对选手负担挺大。比赛时长 10 天，共 18 题。每题总时限 50s，共 10 个测试点，每个测试点的得分与通过人数成反比。因此，虽然暴力通常能过多个点，但暴力能过的点分数都较低，最后几个大数据点分数较高。
通过全部测试点后，运行时间向下取整后最快的人可以获得双倍的分数。提交次数不限而且重复提交没有罚时。可想而知，所有人都会不停刷时间，最后就比谁的常数卷得快。
另外就是，比赛只允许用 Python 3.8 提交，而且没有第三方库。每道题需要实现为一个函数，返回答案。通常返回值都是字符串或者整数，所以遇到答案是实数的情况，要么会取整，要么会表示为分数，要么保留若干位小数表示成字符串。
到比赛截止，我排到了第 12 名，18 道题一共做出来 14 道，其中 6 道时间最快。代码在 这个 repo 里。
A1: Hello, World!
就是 a + b problem。
A5: Spacedogs
题意：给定 $k$ 维空间中 $n$ 个点的初始质量和位置。每轮合并质量最小的两个点，合并后的点位于两点连线中点处，质量为二者之和。重复合并至只剩一个点为止，输出其坐标。$n\leq 10^4,\ k\leq 5$。
题解：用 k-d tree 加速模拟就行。我不会写 k-d tree，直接在 GitHub 上找了个库往上贴。最后跑了 23s，是最快提交的四倍。
A7: Doubling Danny
题意：求 $\sum_{i=1}^n 2^{a_i} \bmod{m}$，其中 $n\leq 5000,\ a_i\leq 2^{5000},\ m\leq 2^{2203}-1$ 且 $m$ 为质数。
题解：这模数实在有点大，整得我有点懵。最直观的想法是首先把 $a_i$ 都对 $m-1$ 取模，然后快速幂，但这样没法过所有点。之后就是往上堆常数优化，比如十进制快速幂，还有对指数排序后做差，每次只算差值次幂然后累乘。这两个优化都加上之后可以 41s 通过，但一众人的提交都是 0s 过的，不知道是什么黑魔法。
A9: Jumping Jimmy
题意：很裸的静态 RMQ 问题，$n\leq 10^5$。
题解：用 Sparse Table（ST 表，似乎没有更好的中文名称）就能过，但跑不到最快。但毕竟是经典问题，网上能搜到 一些 课件，里面提到可以通过恰当分块，块内暴力块间 ST 表做到 $O(n)$ 预处理 $O(\log n)$ 询问，这样就可以 1s 通过成为最快提交了。理论最优复杂度可以做到 $O(n)-O(1)$，但常数上未必有分块暴力快。
A12: Dicey Situation
题意：有 $d$ 个一模一样的 $k$ 面骰子，第 $i$ 面上有数字 $a_i$。Alice 首先掷全部骰子，然后她可以重掷 $r-1$ 轮。每轮中，她可以选择任意数量的骰子（包括全选和全不选）保持不变，将剩下的骰子重新掷一遍。Alice 结束后，Bob 进行同样的操作（掷全部骰子，然后重掷 $r-1$ 轮）。最后比较两人的骰子点数和，较大的一方得 1 分，如果相等则都得 0 分。双方都想最大化自己减去对方的分数，并都采取最优策略。求 Bob 分数减去 Alice 分数的期望值。$d,r\leq 8,\ k\leq 6,\ 1\leq a_i\leq 20$。
题解：这题很有意思。首先 Bob 是有优势的，他可以根据 Alice 掷出的点数和决定每轮重掷哪些骰子。其次，双方如果要重掷骰子，那么一定会选择点数最低的若干颗。
假设已知 Alice 按照最优策略掷出每种点数和的概率，我们可以 DP 求出 Bob 的期望收益。首先枚举 Alice 的点数和，记为 $A$。令 $f[i][S]$ 表示还剩 $i$ 次重掷，目前骰子点数的状态为 $S$ 时的期望收益。所有初值 $f[0][S]$ 直接与 $A$ 比较就能求出。对 $i>0$ 的情况，枚举重掷的骰子数量 $j$，求出只保留点数最大的 $d-j$ 颗骰子之后的状态 $S’$，再枚举重掷 $j$ 颗骰子能掷出的所有点数组合即可转移。$S$ 的方案数其实相当于 $d$ 个无标号小球放入 $k$ 个有标号盒子的方案数，为 $\binom{d+k-1}{k-1}$，最大为 1287。这样可以求出 Bob 在 Alice 点数和为 $A$ 时的期望收益 $B(A)$。
而对于 Alice 的策略，一开始的想法是：Alice 的目标就是掷出尽可能大的点数和，因此每个骰子可以独立计算。但事实上并非如此，Alice 的策略与其当前点数和有关。举个例子，Alice 有 3 个每面为 $[1,2,3]$ 的骰子，其中一颗的点数为 2。如果剩下两颗的点数为 $[1,1]$，那么重掷这颗骰子的期望收益的增量为 $(B(3)+B(5)-2B(4))/3$；如果为 $[3,3]$，则期望收益为 $(B(7)+B(9)-2B(8))/3$。而这两个值未必相同，只有当这个值大于 0 时，Alice 才会重掷这颗骰子。因此，我们应当用与 Bob 相同的 DP 来求 Alice 的期望收益，初值 $f[0][S]$ 为 $B(S\text{ 的点数和})$。
剩下的就是一些常数优化了。比如，用 $3k$ 个 bit 表示状态 $S$；缓存每个 $S’$ 转移得到的结果避免重复计算；当 $S$ 的点数和大于 $A$ 时期望收益一定为 1。加上优化之后可以 25s 通过，但最快提交只花了 5s。
A13: Explodium!
题意：给定数轴上 $n$ 个目标的位置 $p_i$ 及其权重 $s_i$，你需要扔若干炸弹摧毁所有目标。落在 $x$ 处且能量为 $g$ 的炸弹对目标 $i$ 造成的伤害为 $\max(0,g-\vert x-p_i\vert)$。一个目标受到的总伤害是来自每枚炸弹的伤害之和，总伤害达到 $s_i$ 则其被摧毁。求炸弹能量和的最小值。$n\leq 10^5$。
题解：一个很关键的结论是：最优方案中，每个目标只会被一个炸弹炸到，也即每个炸弹的“杀伤范围”一定不重合。假设有两个炸弹都能炸到位于其间的某个目标，那么改成在目标位置放一个炸弹覆盖相同的区间，需要的能量是更低的。
基于结论，可以得到很显然的 DP：令 $f[r]$ 表示覆盖前 $r$ 个目标的最小能量和，转移时枚举 $l$ 然后考虑一个炸弹覆盖 $[l,r]$ 的区间所需的能量。计算能量时，可以枚举能量所在的范围，假设为第 $k$ 到 $k+1$ 个目标之间，那么最小能量为其左侧的 $s_i-p_i$ 的最大值加右侧的 $s_i+p_i$ 最大值，即 $\max_{l\leq i\leq k} (s_i-p_i)+\max_{k<i\leq r} (s_i+p_i)$，同时还得保证按照这一能量算出来的炸弹位置确实在 $[k,k+1]$ 之间。朴素实现的复杂度为 $O(n^3)$。
能量计算的过程可以进一步优化。考虑相邻的两个目标 $i$ 和 $j$，如果 $s_i-s_j\geq \vert p_i-p_j\vert$，那么可以摧毁 $i$ 的炸弹必然可以同时摧毁 $j$，因此可以直接删去 $j$。这样一来，计算覆盖区间所需能量时，左右侧取到最大值的目标必然是端点处的目标。化简转移方程后，直接维护前缀最值即可 $O(1)$ 转移，总复杂度 $O(n)$，可以 0s 通过。
A15: Grand Hotel
题意：酒店有编号 $0\sim n-1$ 的房间，初始为空。有 $m$ 次操作，操作共两类：
- 入住：给定 $x$，找到编号连续且起始编号最小的 $x$ 个空房间，标记为非空。
- 退房：给定 $i$，将第 $i$ 次入住操作标记的房间标为空。
求每次入住时标记的编号最小的房间的编号和。$n\leq 10^{11},\ m\leq 10^6$。
题解：我写了一个 $O(n\log n)$ 的做法，没能通过最后一个测试点。做法大致是，维护所有连续的空区间，然后维护若干哈希表，允许快速查询：左端点为 $l$ 的区间右端点、右端点为 $r$ 的区间左端点、长度为 $d$ 的所有区间的有序列表（只关心最小值，可以用堆）。另外，再用线段树维护长度 $\geq d$ 的所有区间中左端点的最小值，在更新哈希表的时同时维护。可想而知常数不小。
大多数提交都花了超过 30s，最快的只要 11s。很难想象有 $O(n)$ 的做法，估计是有常数更小的实现吧。
A16: Roshambolic
冷知识：题目名字是一个“混成词”（portmanteau），是由 roshambo（石头剪刀布）和 shambolic（混乱的）重叠拼起来的。Roshambo 是美国加州北部常用的叫法，据说来源自日语里的「じゃん拳ぽん」（jyan-ken-pon），于二十世纪初传到美国。而据明代文献记载，石头剪子布则是最早起源于中国的游戏。
题意：题意大概是两人用牌玩石头剪刀布，每张牌上写了石头、剪刀，或者布。给定牌的顺序，双方轮流打出牌堆顶的牌，胜者获得这两张牌并加入牌堆底，平局则各自收回。问多少回合后有一方没牌。牌数$\;\leq 1000$。
题解：很直接的模拟题，但要跑最快（2s）还是需要一些实现技巧。
D1: Gone to Seed
题意：$2^k$ 个选手进行淘汰赛，每轮中两两配对并淘汰败者，$k$ 轮后决出冠军。给定每个选手的能力 $s_i$，两人 $i$ 和 $j$ 对战，$i$ 胜的概率为 $s_i/(s_i+s_j)$。求 0 号选手获胜的概率，以最简分数形式表示。$k\leq 4,\ 1\leq s_i\leq 20$。
题解：状压 DP，用 $f[i][S]$ 表示集合 $S$ 中的人进行淘汰赛，最后 $i$ 胜出的概率。转移时枚举 $S$ 的大小为 $\vert S\vert/2$ 的子集，再枚举两个子集各自的胜者进行转移，最后答案为 $f[0][\text{全集}]$。由于我们最后只关心 0 号选手获胜的概率，当枚举的子集中包含 0 时，则只需考虑 0 是胜者的情况，可以少计算很多状态。
分数的处理其实有一些技巧。虽然 Python 内置了 fractions.Fraction 分数类，但其实现中每做一次都会求一次最大公因数，而题目中算到最后分子分母都会变成很大的数，求 gcd 的开销很大。因此，我自己实现了需要手动化简的分数类，只在一个状态的结果算出来之后才化简。为了避免中间过程的分母太大，做加法时特判被加数的分母是否是加数分母的倍数。
最终运行时间 18s，而最快的提交只跑了 7s。
D2: Hardcore Parkour
题意：略。
题解：很简单的 DP，$f[i][j]$ 表示在平台 $i$ 速度为 $j$ 的最小耗时。直接实现的复杂度是 $O(100n)$（10 种速度，转移最多考虑 10 个前一列的平台）。运行时间 6s，最快 1s。用单调队列可以把转移复杂度降为 $O(1)$，但我没写，压压常数估计就能跑进 1s 了。
D3: Wascally Wabbits
题意：有 $n$ 只来自同一家族的兔子，其亲子关系构成一棵树。每只兔子有一对基因控制眼睛颜色，显性基因为 R，隐性基因为 g。当一对基因里有显性基因时（RR 或 Rg），兔子表现出显性性状（红眼）；只有当基因型是 gg 时，才表现出隐性性状（绿眼）。已知在遗传时，每个基因都有 $p$ 的概率变异。给定家族树，以及部分兔子的性状，求绿眼兔子数量的期望值。$n\leq 10^4$，答案需要表示为分数。
题解：期望线性可加，所以我们分开考虑每只未知性状的兔子。三种基因型 RR、Rg、gg 的先验概率分别为 $1/4$、$1/2$、$1/4$，我们要求的是兔子基因型是 gg 的后验概率。由贝叶斯公式，我们可以转而求：当这只兔子基因型是 gg 时，其它兔子的性状与已知相符的概率。注意到这里亲子关系颠倒是没有影响的，所以我们可以以枚举的兔子为根做树形 DP 计算上述概率。以每只兔子为根做一次树形 DP 的总复杂度为 $O(n^2)$，但我们可以用经典的两遍 DFS 方法将其优化至 $O(n)$。
不过这里有个意料之外的问题：分数计算开销实在是太大的。在树高较大的情况下，中间结果可以达到 $p^{2n}$，即便题目约定分母不超过 100，也有四万位了。考虑运算时间的话，实际复杂度应为 $O(n^{2.5})$ 甚至 $O(n^3)$（Python 的乘法实现了 Karatsuba 算法，复杂度为 $O(n^{1.58})$；gcd 的复杂度不清楚）。维护 $p$ 的多项式复杂度上和直接做分数运算没有太大差别，常数反而更大，因此也意义不大。
最后我只结合了 D1 中的手动化简分数实现了 $O(n)$ 的 DP，通过了 8 个点。最快的提交居然只要 1s，过于恐怖。
D4: Task Genie
题意：给定 $n$ 个节点的树，每个节点有正整数权重 $c_i$。你可以选择最多 $w$ 个节点，将其权重改为 0。问修改后，从根节点出发的最长链最短是多少。链的长度定义为途径节点的点权和。$n\leq 10^5,\ w\leq 5\cdot 10^4,\ c\leq 10^3$。
题解：这题我只会写暴力。我就实现了一个 $O(nw^2)$ 的树上背包，过了 7 个点。我猜正解是某种数据结构优化的贪心加调整，但我没有证据。
D5: Snakes and Ladders
题意：“蛇与梯子”是一款经典的 无聊 桌游。棋盘上有 $n$ 个格子，0 为起点，$n-1$ 为终点。玩家掷骰子前进，当停留在梯子的起点时，则前进到梯子的终点；当停留在蛇的起点时，则后退到蛇的终点。共有 $l$ 个梯子和 $s$ 条蛇，所有蛇和梯子的起点、终点均不重合。问期望情况下需要多少步到达终点。$n \leq 10^5,\ 1\leq s,l\leq 100$。
题解：求图上随机游走的期望步数是一类经典问题。本题中，如果没有蛇，那么图构成有向无环图，可以直接 DP 计算期望。有蛇则出现了环，需要列方程组后高斯消元求解，复杂度为 $O(n^3)$。设格子 $i$ 走到终点的期望步数为 $x_i$，则方程为 $x_i=\frac{1}{6}\sum_{j=1}^6 x_{p_{i+j}}+1$，其中 $p_i$ 代表停在第 $i$ 个格子时会移动到哪里，如果格子是梯子的起点则移动到其终点；否则停留在原地。
可以注意到，方程组中的绝大多数方程都是“平凡”的。如果格子 $i$ 不是蛇的终点，那么 $x_i$ 只会出现在序号 $i$ 之前的方程中，因此我们可以直接将其代入从而消去变量 $x_i$，最后只剩下蛇的终点所在格子对应的 $l$ 个变量。这一过程可以用 $O(nl)$ 的 DP 实现，之后只需 $O(l^3)$ 的时间求解简化的方程组即可。至此，已经可以 10s 通过了。
但这题最快的提交是 0s，事实上也确实可以继续优化。目前的瓶颈在于 $O(nl)$ 的 DP，但可以注意到，DP 的大部分过程同样是在做“平凡”的转移，即计算之后 6 个格子的系数然后除以 6。把这一转移写成矩阵形式并预处理系数，则可以在 $O(6l)$ 的时间内完成连续一段的平凡转移，那么复杂度可以降为 $O(l^2)$。最终运行时间应该在 1s 左右，运气好刷几次可以刷成 0s。可惜的是，比赛结束后官方重测所有提交，我的运行时间又掉回了 1s。
D6: Two Quests
题意：给定两个序列 $a$ 和 $b$，长度分别为 $n$ 和 $m$。要求将两个序列合并为一个长度为 $n+m$ 的序列 $c$，要求新序列内来自 $a$ 的元素相对顺序不变，$b$ 同理。求 $\vert c_1-0\vert+\sum_{i=2}^{n+m} \vert c_i-c_{i-1}\vert$ 的最小值。$n,m\leq 2000$。
题解：令 $f[i][j][0/1]$ 表示已经选择了序列 $a$ 的前 $i$ 个元素和 $b$ 的前 $j$ 个元素，且上一个选择的元素来自序列 $a$ 或 $b$（$0/1$）的最小值。转移时枚举下一个选择的元素来自 $a$ 还是 $b$ 即可。这样可以 20s 左右通过。
进一步优化也不难。按照对角线顺序（$i+j$）转移，则可以将空间复杂度优化到 $O(n+m)$。由于 Python 没有原生的二维数组，空间上的优化可以大幅减少寻址时间。再加上其它一些常数优化，可以把运行时间压到 8s。直到比赛最后一天前，这都是最快的提交，可最后一天被人卷出了 6s，而我已经不知道自己的代码还要怎么榨出性能了。
D8: Garden Path
题意：$n\times m$ 的格子中有 $k$ 个格子上有障碍物，问用 $1\times 2$ 的砖块铺满剩下格子的方案数，取模输出。$n\leq 6,\ m\leq 10^9,\ k\leq 1000$。
题解：很经典的骨牌密铺问题，有个很经典的状压 DP 矩阵快速幂做法。状态表示比较巧妙，我们只需要记录一行中每个格子是否是竖直摆放的骨牌的上半部分即可。考虑两个二进制数表示的状态 x 和 y，x 能向 y 转移当且仅当：
x & y == 0：相邻行的同一列不能有两个竖直摆放的上半部分。x | y的所有连续 0 位长度为偶数。y的 1 位自然是被竖直的骨牌占据了，同样，x的 1 位在y也需要对应的骨牌下半部分。剩下的位置必须被水平的骨牌占满，因此每段的长度必须为偶数。
障碍物则可以类似考虑。之后便是用矩阵快速幂加速转移连续的不含障碍物的行，复杂度为 $O(2^{3n}k\log m)$。要优化到 0s 通过，则需要下一番功夫做常数优化。首先则是预处理转移矩阵的次幂并打表。用 Python 打表其实很方便，直接 pickle.dumps 就完事儿。在做快速幂时，注意到我们其实是用行向量左乘矩阵的次幂，因此我们优先做矩阵和向量的乘法，将快速幂优化到 $O(2^{4n}\log m)$。用稀疏矩阵计算还可以进一步优化常数。最后再预处理一行内每种障碍物情况下的转移（稀疏）矩阵并打表，方可强压在 0s 内通过。但这个成绩也不稳定，赛后重测又给我整成了 1s。
D10: Paper Cut
题意：有一张 $c\times d$ 的纸，要将其裁剪成每块大小 $a\times b$ 的小块。每次操作可以选择一块并沿网格线将纸裁成两块。问是否可以按要求完成裁剪。$c,d< 10^{12},\ a,b<10^6$，最多 1000 组询问。
题解：这题我其实是找规律做出来的。先上结论，可以完成裁剪的情况需要满足至少一个条件：
- $c$ 是 $a$ 的倍数，且 $d$ 是 $b$ 的倍数。
- $c$ 是 $\mathrm{lcm}(a,b)$ 的倍数，且 $ax+by=d$ 有非负整数解。
- 条件 1 或 2 中，交换 $c$ 和 $d$。
条件 2 要满足的前提是 $d$ 是 $\gcd(a,b)$ 的倍数。可以用拓展欧几里得算法求出 $ax+by=\gcd(a,b)$ 的一组解 $(x_0,y_0)$，那么 $(\frac{x_0d+kb}{\gcd(a,b)},\frac{y_0d-ka}{\gcd(a,b)})$ 同样是一组解，判断是否有整数 $k$ 使得解非负即可。运行速度很快，可以 0s 通过。
知道结论后，再回头尝试证明。充分性很好证明，考虑必要性。我们将所有可以完成裁剪的 $(c,d)$ 分成两类，一类是裁出的所有 $a\times b$ 小块”朝向“相同的，即满足条件 1，另一类则是裁出来朝向不同的。用归纳法加一大堆分类讨论可以证明第二类与条件 2 等价，这里略去。不过我自己只是脑补了一下，没有细想，不太清楚是不是严格的证明。直观理解一下，条件 2 代表可以将纸裁成两部分，每部分都递归满足条件 2，也可以是一部分水平切割，另一部分竖直切割。
D11: Satisfaction
题意：给定包含 $n$ 个布尔变量的布尔表达式，仅包含与或非三种运算和括号。求所有 $2^n$ 种取值组合中，有多少组可以让表达式值为真。$n\leq 26$，表达式长度不超过 1000。
题解：这题我写的暴力。暴力非常好写，用 Python 的 compile 和 eval 就行，甚至不用自己写 parser。加一些常数优化，最多可以过 8 个点。我还探索了一些别的做法，比如 parse 成语法树之后尝试一些简单的化简，但效果甚微。
这一类布尔可满足性问题是 NPC 的，所以我猜正解也就是搜索加剪枝。搜索时优先搜索包含变量少的子树，可能可以找到一组变量，使得其取特定值时整个表达式恒真或恒假。举个例子，如果 AND 节点的一个儿子只包含一个变量，那么该变量为假时整棵子树为假，这样可以大幅减小搜索空间。不过我并没有写这个做法，感觉上也并不太好写。
D14: Prime Feast
题意：给定长度为 $n$ 的数字串，每次从中删去一个长度不超过 4 的子串，满足子串不含前导零、是个质数，且比前一次删去的数字要小。问删去的所有数字之和最大是多少。$n\leq 100$。
题解：如果没有删除的数字递减的限制，则可以用区间 DP，转移有两种情况，要么是把区间分成两半分开处理，要么是区间两个端点会被一起删掉。如果是后者，则枚举删去的数字长度，然后再枚举区间中间最多两个位置。复杂度 $O(n^4)$。
但有数字递减的限制就比较麻烦了，不知道是否还有巧妙的 DP 做法。最后我实现的是搜索，只要加上最优性剪枝就能跑得贼快，甚至可以 0s 通过。感觉有点不够优美。