AtCoder Grand Contest 044 题解

AutumnKite

题解AtCoder

发布于：2020年9月8日

次浏览

比赛地址

A - Pay to Win

题意

你要通过以下操作将 \(0\) 变成 \(N\)：

• 乘 \(2\)，花费 \(A\)；
• 乘 \(3\)，花费 \(B\)；
• 乘 \(5\)，花费 \(C\)；
• 加 \(1\) 或减 \(1\)，花费 \(D\)。

求最少操作次数。

\(N\le 10^{18},A,B,C,D\le 10^9\)

题解

考虑倒着做。假设当前的 \(N\) 要除以 \(v\)，那么一定是转移到 \(\lfloor\frac{N}{v}\rfloor\) 或 \(\lceil\frac{N}{v}\rceil\)。

注意到这样子转移遇到的状态一定是 \(\lfloor\frac{N}{2^a3^b5^c}\rfloor\) 或 \(\lceil\frac{N}{2^a3^b5^c}\rceil\)，所以状态数是 \(O(\log^3 N)\) 的。

注意转移时需要考虑 \(N\to N/v\) 时可能直接减的花费更小，需要与直接减的花费取 \(\min\)。

时间复杂度 \(O(\log^3 N)\)，如果使用 map 则复杂度为 \(O(\log^3 N\log \log N)\)。

代码

B - Joker

题意

有一个 \(N\times N\) 的矩阵，每个位置上有一个人，编号从上到下从左到右依次是 \(1,\ldots,N^2\)。

人会一个一个地离开（即从所在位置每次向上下左右移动直到走出矩阵），第 \(i\) 个离开的人编号为 \(P_i\)。

当一个人离开时，一条路径的权值为路径上还没有离开的人的数量。每个人会选择权值最小的路径离开。

求最小权值之和。

\(N\le 500\)

题解

考虑模拟这个过程，并同时维护 \(f(i,j)\) 表示 \((i,j)\) 走到矩阵外的最小路径权值。

每次当 \((x,y)\) 位置的人离开后，\(f(x,y)\) 减 \(1\)，会连带其他位置的 \(f\) 值改变。

但是注意到开始时 \(\sum f(i,j)\le N^3\)，所以我们只要每次暴力把需要更新的 \(f\) 修改即可。

时间复杂度 \(O(N^3)\)。

代码

C - Strange Dance

题意

有一个长度为 \(3^N\) 的序列 \(P_0,\ldots,P_{3^N-1}\)。有 \(|T|\) 次操作，操作有两种：

• \(T_i=\mathtt{R}\)，对于所有 \(0\le i < 3^N\)，执行 \(P_i\gets (P_i+1)\bmod 3^N\)。
• \(T_i=\mathtt{S}\)，对于所有 \(0\le i < 3^N\)，将 \(P_i\) 的三进制表示下的 \(1\) 改成 \(2\)，\(2\) 改成 \(1\)。

求最后的序列 \(P\)。

\(N\le 12,|T|\le 2\times 10^5\)

题解

考虑从低位到高位建立 Trie。

对于 \(\mathtt{R}\) 操作，可以从 Trie 的根节点开始，将 \(0\) 改成 \(1\)，将 \(1\) 改成 \(2\)，将 \(2\) 改成 \(0\)，然后递归原来 \(2\) 的子树即可。

对于 \(\mathtt{S}\) 操作，可以直接在根节点打上标记，在需要递归时下传即可。

时间复杂度 \(O(3^N+|T|N)\)。

代码

D - Guess the Password

题意

这是一个交互题。交互库有一个长度不超过 \(L=128\) 的字符串 \(S\)。你可以每次询问交互库不超过 \(Q=850\) 次以下询问来得到 \(S\)：

• 给出一个长度不超过 \(L\) 的字符串 \(T\)，交互库会返回支持插入字符、删除字符、修改字符时 \(S\) 到 \(T\) 的最少操作次数（即编辑距离）。

字符集为所有大写字母、小写字母和 \(0\) 到 \(9\) 的数字。

题解

首先我们可以通过询问形如 \(\underbrace{aa\ldots a}_{L}\) 的字符串求出字符 \(a\) 的出现次数，即设返回值为 \(x\)，则 \(a\) 的出现次数为 \(L-x\)。

然后我们假设 \(S_1,S_2\) 是 \(S\) 的两个不相交的子序列，考虑如何合并成一个长度为 \(|S_1|+|S_2|\) 的子序列。

我们可以将 \(S_2\) 中的字符依次插入 \(S_1\) 中，询问次数约为 \(|S_1|+|S_2|\)。

于是我们可以对字符集分治，然后每次合并，询问次数约为 \(L\log_2 |\Sigma|\)，可以通过。

代码

E - Random Pawn

题意

有一个长度为 \(N\) 的环，环上的点顺时针编号为 \(1\) 到 \(N\)。

初始时会在所有点中等概率随机一个位置放一个棋子。

假设当前棋子在 \(p\)，可以执行两种操作：

• 获得 \(A_p\) 的收益，结束游戏。
• 花费 \(B_p\)，将棋子等概率移动到相邻两个位置之一（即各 \(\frac{1}{2}\)）。

求最大的期望收益，精度要求 \(10^{-10}\)。

\(N\le 2\times 10^5\)

题解

如果我们到达 \(A_i\) 最大的位置，那么可以直接结束游戏，所以我们可以断环成链。

考虑 \(B_i=0\) 的情况，令 \(f_i\) 为从 \(i\) 出发的最大期望收益。

假设我们钦定到达 \(S=\{x_1,x_2,\ldots,x_k\}\ (x_i < x_{i+1})\) 集合中的点时结束游戏，到达其他点则继续移动，那么对于 \(i\not\in S\) 的情况，有 \[ f_i=\frac{f_{i-1}+f_{i+1}}{2} \] 移项后得 \[f_{i+1}-f_i=f_i-f_{i-1}\]

也就是说，对于 \(u=x_j\le i\le x_{j+1}=v\)，这些 \(f_i\) 组成了一个等差数列。那么我们有 \[\sum_{i=u}^{v} f_i=\frac{(A_u+A_v)(v-u+1)}{2}\]

那么所有 \(f_i\) 之和可以看做是 \((x_i,A_{x_i})\) 这些点顺次相连的折线下方的若干梯形面积之和加上一个定值。

为了使这个和最大，这些点一定是 \((i,A_i)\) 的上凸壳上的顶点。

接下来我们一般情况。

考虑令 \(f_i'=f_i-C_i\)，那么有 \[ f_i'= \begin{cases} A_i-C_i & \text{if } i\in S\\ \frac{f_{i-1}+f_{i+1}}{2}-B_i-C_i=\frac{f_{i-1}'+f_{i+1}'}{2}-B_i-C_i+\frac{C_{i-1}+C_{i+1}}{2} & \text{otherwise} \end{cases} \]

我们只要使得 \(C_i\) 满足 \(\frac{C_{i-1}+C_{i+1}}{2}-C_i=B_i\) 即可转化为 \(B_i=0\) 的情况。

这样的 \(C_i\) 可以很简单的递推构造。

时间复杂度 \(O(N)\)。

代码

F - Name-Preserving Clubs

题意描述较为复杂，请直接查看原题面 Formal Statement 部分。

题解

首先我们强制 \(L\) 中的集合互不相同。

考虑建立一个 \(k\times n\) 的矩阵，每一位填 \(0\) 或者 \(1\)。称一个矩阵是好的当且仅当行与行之间互不相同，并且任意打乱列后得到的矩阵都不能通过原矩阵打乱行得到。

显然好的矩阵和题目中的 name-preserving configuration 一一对应。

假设一个矩阵 \(A\) 是好的，我们可以观察到下面两个性质：

• \(A\) 的转置是好的。
• 考虑 \(2^k\) 种不同的列，由其中所有不在 \(A\) 中的列任意排列构成的矩阵也是好的。

那么如果我们设 \(c(k,n)\) 表示本质不同的 \(k\times n\) 的好的矩阵数量，那么有 \(c(k,n)=c(n,k)=c(k,2^k-n)\)。

令 \(g(n)\) 表示最小的 \(k\) 满足 \(c(k,n)>0\)。

令 \(G(n)\) 满足 \(G(1)=0\)，\(G(n)\) 表示最小的正整数 \(k\) 满足 \(2^k-n\ge G(k)\)。

我们可以用 \(G(n)\) 的若干性质，通过归纳和构造证明 \(G(n)=g(n)\)。

另外，我们还可以用构造证明对于 \(6\le k\le n\) 时有 \(c(k,n)>1000\)。

于是我们只需要考虑 \(k\le 5,n\le 2^{k-1}\) 的情况。暴搜后打表即可。

对于原题 \(L\) 中的集合可以互不相同的情况，可以证明只有当 \(N=4\) 和 \(N=7\) 时分别会额外增加 \(1\) 种方案和 \(2\) 种方案，特判即可。

上述结论的证明可以参考官方题解。

代码

更新于：2020年9月13日

构造

数学

分治

搜索

凸包

记忆化搜索

trie

交互