A. Arrested Development
动态规划，$f(i,j)$ 表示考虑前 $i$ 个任务，第一个人总时间为 $j$ 时，第二个人总时间的最小值。
时间复杂度 $O(n^2\max\{a_i,b_i\})$。
B. Champernowne Substring
讨论以下情况：
对于位置不超过 $100\,000$ 的情况暴力判断，以下都假设串中出现的都至少是五位数。
特判串中出现 $10^k$ 或 $10^k-1$ 的情况，以下都假设串中所有数的长度相等。
串中只包含一个数。问号一定贪心填 $0$（首位是 $1$），如果首位是 $0$ 还需要在前面补 $1$。
串中包含超过一个数。枚举这个数的开始位置和长度，以及进位的位数（因为串长不超过 $25$ 且都至少是五位数，因此至多有一次进位）。那么进位的部分全部填 $0$ 或 $9$，前一位枚举 $0$ 至 $9$，再之前的位每个数都一样，问号同样贪心填 $0$ 或 $1$。对于每种可能性都检查一遍。
C. Comparator
首先注意到，表达式只有两个输入，我们可以直接枚举这两个输入后求表达式的值。从而，每条语句的效果都可以拆分为不超过 $4$ 条：如果 $x$ 的第 $a$ 位为 $u$ 且 $y$ 的第 $b$ 位为 $v$，则返回 $r$。当两条语句的 $(a,u,b,v)$ 四元组相同时，靠后的语句实际上没有任何效果，因为它所能作用的输入已经全部返回了。因此，我们实际上只需要考虑不超过 $4k^2$ 条语句，每条语句的效果可以在 $O(2^{2k})$ 的时间内暴力处理。
当我们得到了所有 $f(x,y)$ 的值后，就可以统计答案。前两个答案都可以暴力统计，最后的答案枚举 $x,y$ 后使用 bitset 优化即可。
时间复杂度 $O\left(\sum|expr|+k^22^{2k}+2^{3k}/w\right)$。
D. Dihedral Group
二面体群的操作对应到字符串其实就是翻转和循环移位，只需要判断未翻转/翻转的 $d+d$ 是否包含 $t$ 作为子串。
时间复杂度 $O(n)$。
E. House Deconstruction
1. $n=m$ 的情况
首先考虑 $n=m$ 的情况，即人的数量和房子的数量一样多时，如何求最小代价。对于一个方案，设 $c_i$ 表示经过了 $i$ 到 $i+1$ 这条边的人数（这里模 $x$ 相等的下标表示同一个位置，例如 $x+1$ 代表 $1$）。如果是从 $i+1$ 到 $i$ 则 $c_i$ 是经过人数的相反数，显然最优解中不会有一条边两个方向都有人经过。则方案对应的代价是 $\sum_{i=1}^x|c_i|$，需要满足的限制如下：
- 如果 $i$ 位置是人，则 $c_i=c_{i-1}+1$。
- 如果 $i$ 位置是房子，则 $c_i=c_{i-1}-1$。
- 如果 $i$ 位置是空，则 $c_i=c_{i-1}$。
容易发现，$c_i$ 序列几乎是确定的，除了可以整体加上一个任意整数。设一个合法的序列是 $c_i'$，则最小代价为对于任意 $k$，$\sum_{i=1}^x|c_i+k|$ 的最小值。这个函数关于 $k$ 是下凸的，因此可以用三分求出答案。（事实上，$k$ 一定是 $c_i$ 的中位数的相反数。）
2. $n< m$ 的情况：最优解
延续 $n=m$ 的思路，我们可以稍微修改 $c_i$ 的定义，即如果 $i$ 位置是房子，$c_i$ 可以等于 $c_{i-1}-1$ 或 $c_{i-1}$（表示该房子未被选择）。我们可以猜测以下的引理：
引理 1 设 $g(k)$ 为 $c_x=k$ 时的最优解，则 $g(k)$ 是下凸函数。
有了引理 1 之后，对于 $n< m$ 的情况我们同样可以三分 $k$，之后只需解决固定 $c_x$ 之后的问题，即可求出最优解。
引理 1 的证明 只需证明 $2g(k)\le g(k-1)+g(k+1)$。设 $k-1$ 和 $k+1$ 对应的序列分别为 $c_i^{(k-1)}$ 和 $c_{i}^{(k+1)}$。则令 $c_i^{(k)}=\frac{c_i^{(k-1)}+c_i^{(k+1)}}{2}$。该序列几乎满足我们的需求，包括 $c_x^{(k)}=k$ 以及相邻 $c_i$ 之间的关系，并且因为三角形不等式 $|a+b|\le |a|+|b|$，该序列的代价不超过 $\frac{g(k-1)+g(k+1)}{2}$。唯一有问题的地方是当某一处房子只在 $k-1$ 和 $k+1$ 中的一个方案中被选择时，我们会算出 $c_i=c_{i-1}-1/2$。然而，对于每一个极长的小数部分为 $1/2$ 的连续段，整体加上或减去 $1/2$ 就是合法的序列，且其中的一种不会使得代价变大（只需比较正数和负数的数量）。从而我们证明了 $2g(k)\le g(k-1)+g(k+1)$。$\blacksquare$
对于证明中存在小数部分的调整，事实上，即使我们把 $i$ 位置是房子时的限制改为 $c_i\in[c_{i-1}-1,c_i]$，最优解仍然会在所有数都是整数时取到。（提示：仍然可以考虑调整，也可以直接把原问题写成费用流，这样也能得到原问题的凸性。）
接下来只需要考虑固定 $k$ 时如何求最优解。我们可以使用 DP。
设 $f(i,j)$ 表示考虑了前 $i$ 个位置，$c_i=j$ 的最小代价。初始值为 $f(0,k)=0$。转移如下：
- 如果 $i$ 位置是人，则 $f(i,j)= f(i-1,j-1)+|j|$。
- 如果 $i$ 位置是房子，则 $f(i,j)= \min \{f(i-1,j+1),f(i-1,j)\}+|j|$。这里代表房子可选可不选。
- 如果 $i$ 位置是空，则 $f(i,j)=f(i-1,j)+|j|$。
最终的答案即为 $f(x,k)$。
注意到 $f(i,j)$ 对于固定的 $i$，关于 $j$ 是下凸的，很容易维护。实现中，为了方便，可以把状态改为 $f(i,j)$ 表示前 $i$ 个位置选了 $j$ 个房子的最小代价，这时最小值的位置一定是单调不降的，可以用差分维护最小值之后的斜率，对于房子只需插入一个 $0$ 的斜率。
把空的位置一起处理，就能做到 $O(m)$ 的时间复杂度。
因此，我们可以在 $O(m\log n)$ 的时间内求出最优解。
3. $n< m$ 的情况：方案数
为了计算方案数，我们还需要以下的引理：
引理 2 一个全局最优解 $S$ 只会在唯一的 $k$ 处取到最优解。
证明 注意到对于一个全局最优解的匹配方案，每个未选择的房子 $i$ 都应该满足 $c_i=0$，即没有匹配经过该房子，否则用该房子替换这个匹配中的房子，代价严格变小。如果一个全局最优解 $S$ 在两个不同的 $k$ 处取到最优解，那么一定有一个 $k$ 使得某个未选择的房子 $i$ 满足 $c_i\ne 0$，矛盾。因此， 一个全局最优解 $S$ 只会在唯一的 $k$ 处取到最优解。$\blacksquare$
根据引理 2，我们只需对每个 $g(k)$ 取到最小值的 $k$ 分别计算方案数并求和即可。
我们还需要以下引理：
引理 3 至多有两个 $k$ 满足 $g(k)$ 是最小值。
证明 采用反证法，假设 $g(k-1),g(k),g(k+1)$ 都是最小值。根据引理 1 的证明过程，$g(k)=\frac{g(k-1)+g(k+1)}{2}$ 的必要条件是 $c_i^{(k-1)}\cdot c_i^{(k+1)}\ge 0$（否则三角形不等式严格不等），以及对于每个极长的小数部分为 $1/2$ 的连续段，正数的个数等于负数的个数（从而无论加还是减 $1/2$，都不会改变代价）。因此不妨设 $k-1\ge 0$（$k+1\le 0$ 是对称的），找到最小的 $j$ 满足 $c_j^{(k-1)}\ne c_j^{(k+1)}-2$，则 $j$ 位置是房子。这样的 $j$ 一定存在，否则两个方案对应相同的 $S$，根据引理 2，一定不是全局最优解。此时 $c_j^{(k-1)}=c_j^{(k+1)}-3$ 或 $c_j^{(k-1)}=c_j^{(k+1)}-1$，且 $c_j^{(k-1)}\ge 0$。无论如何，我们都可以令 $c_{j}^{(k)}=c_{j-1}^{(k)}>0$，同时调整极长的连续段。但是因为 $j$ 是未选择的房子，所以这一定不是全局最优解。因此至多有两个 $k$ 满足 $g(k)$ 是最小值。$\blacksquare$
根据引理 3，我们只需要对至多两个 $k$ 分别计算方案数并求和。因此这不会增加我们的复杂度。
至于计算方案数，可以在 DP 的过程中同时进行。我们维护 DP 取到最小值的位置，并且最小值至多有两个。最小值之后的部分的方案数只需进行一个平移。因为最小值的位置单调不降，方案数也很容易维护，时间复杂度仍然为 $O(m)$。
综上，我们可以在 $O(m\log n)$ 的时间复杂度内解决该问题。
F. Magic Bean
我们只需要构造出能够交换两个环内的豆子的操作，之后每次找到 $a$ 环内的 $b$ 豆子，和 $b$ 环内非 $b$ 的豆子交换，即可在不超过 $30$ 次交换内完成复原。
构造的操作如下：把 $a$ 环内要交换的豆子移至 $1$，$b$ 环内要交换的豆子移至 $4$，$a$ 环转到 $b$ 环，$b$ 环逆时针转一格，$b$ 环转到 $a$ 环。
G. Manhattan Walk
由于每个格子的状态是均匀独立随机的，并且到一个格子之前无法得知该格子的状态，因此可以看做到每个格子时再均匀随机状态。
设 $f(i,j)$ 表示从 $(i,j)$ 开始，到达终点的期望最小时间。如果 $i=r$ 或 $j=c$，则可以直接转移，否则设两个方向的 $f$ 值分别为 $a$ 和 $b$（$a\le b$）。
讨论两种情况：
- $b\ge a+p$，那么无论如何都会选择 $b$，期望为 $a+p/4$。
- $b < a+p$，那么只有当离能走 $a$ 还有超过 $b-a$ 的时间才会选择走 $b$，期望为 $(p-b+a)/2p\cdot b+a/2+(b-a)/2p\cdot (a+b)/2$。（三项分别代表选择走 $b$、可以走 $a$ 时走 $a$、等待后走 $a$ 的期望。）
时间复杂度 $O(rc)$。
H. MountainCraft
注意到斜线的长度等于横向覆盖的长度乘以 $\sqrt 2$。而横向覆盖的长度就是所有 $[x-y,x+y]$ 的并。使用线段树维护即可（维护区间最小值和最小值个数；或者因为减法只是加法的撤销，维护每个结点的覆盖次数）。
时间复杂度 $O(q\log q)$。
I. Not Another Constructive!
我们可以在字符 A 的位置计算贡献，也就是前缀中 N 的数量和后缀中 C 的数量的乘积。因此设 $f(i,N,C,k)$ 表示考虑了长度为 $i$ 的前缀，前缀中 N 的数量为 $N$，后缀中 C 的数量为 $C$，是否能恰好有 $k$ 个 NAC 子序列。可以用 bitset 优化。
时间复杂度 $O(n^3k/w)$。
J. Passport Stamps
第 $i$ 趟旅行可能无法进行的条件是 $p\le \sum_{j=1}^{i-1}c_j+i\cdot (c_i-1)$，也就是在前面每个章之间留恰好 $(c_i-1)$ 的间隔。
时间复杂度 $O(n)$。
注意，直接计算可能会超过 long long 的范围，需要使用 __int128 或改用除法。
K. Shadow Line
注意到要判断是否只有一片影子，只需要知道每个端点在墙上的位置的相对关系。而这些相对关系只会有 $O(n^2)$ 次变化，也就是在两两的连线与 $x$ 轴交点的位置。算出这些变化的位置之后就可以进行模拟。
只有一片影子的充要条件是对于每个真前缀，下端点的数量大于上端点的数量。因为每次都是交换位置相邻的端点，因此这个条件可以在 $O(1)$ 时间内维护。
要注意的细节包括在有三点共线时的交换顺序，以及 $x$ 轴上的下端点应该始终排在上端点之前。
时间复杂度 $O(n^2\log n)$。
L. Square of Triangles
M. Training, Round 2
设 $f(i,j,k)$ 表示考虑前 $i$ 个题，是否能恰好加 $j$ 次实现水平和 $k$ 次思维水平。注意这里当某个 $(j,k)$ 能达到时，之后都能达到。因此我们对每个 $j$ 维护两个集合：已经能达到的 $k$ 的集合以及已经更新过的 $k$ 的集合。对于每个问题，我们只需找到矩形中能达到但还未被更新过的 $(j,k)$，将 $(j+1,k)$ 和 $(j,k+1)$ 都加入能达到的集合。因为每个 $(j,k)$ 只会被更新一次，所以时间复杂度是 $O(n^2\log n)$。
