====== yukicoder contest 260 (Typical Game Contest) ====== [[https://yukicoder.me/contests/275|比赛链接]] 经典游戏场，全场玩游戏，全场不会玩。 ===== B - シュークリームゲーム（Easy） ===== ==== 题目描述 ==== 有一个 $n \leq 10^5$ 个结点的环，每个节点上有一个数字 $a_i$。一开始，Alice 和 Bob 占领了两个不同的结点 $s, t$，接着从 Alice 开始轮流从与自己占领的结点相邻且未被占领的节点中选择一个占领，直到所有节点都被占领。 定义一个人的收益为占领的所有点 $a_i$ 之和，两人都希望最大化自己的收益与对方的收益之差，求这个差。 ==== 解题思路 ==== 两人占领的一定是环上一段连续的区间。若有人某一端选择超过一半以上未占领的点是最优的，那另一方一定会提早到达该点避免该情况发生，因此最后会变成两人近似地占领各自两侧的一半区间。 记初始时 $s, t$ 之间未被占领的节点分别是 $p$ 和 $q$ 个，分三种情况讨论： - $p, q$ 都是偶数，那么 Bob 下模仿棋，最后两人各占领一半； - $p, q$ 一奇一偶，那么 Alice 优先取奇数的那一侧，接着模仿 Bob 走即可； - $p, q$ 都是奇数，那么 Alice 第一步有两种选择，接下来都只需要模仿 Bob 走即可，因此 Alice 优先选择让差较大一点的那一侧。 ===== C - チャレンジゲーム ===== ==== 题目描述 ==== 有 $n \leq 10$ 个写了数字的卡片 $a_1, a_2, \ldots, a_n$，Alice 和 Bob 轮流从里面选择一个尚存的卡片，若上面的数字为 $x$： * 有 $\dfrac 1x$ 的概率成功，选择者的得分 $+x$，同时移除该卡片； * 有 $1 - \dfrac 1x$ 的概率失败，无事发生。 当所有卡片都取完时，得分大的人获胜；若最终同分，则 Bob 获胜。 求两人在最优策略下，Alice 作为先手的初始胜率。 ==== 解题思路 ==== 可以用一个三进制 $S$ 表示每个点被谁取走、或者是还未被取走的状态，现在考虑如何状态转移。 记 $P(S)$ 为 $S$ 状态下 Alice 先手的胜率，$P(S, i, j)$ 为 $S$ 状态下，Alice 先尝试取走 $i$，Bob 再尝试取走 $j$ 后，Alice 的胜率，则有： $$ P(S) = \max_{i} \min_{j} P(S, i, j) $$ 原理显然：Bob 总会在选 $j$ 时选让自己胜率大的一步走，即 $P(S, i, j)$ 最小的一步，Alice 应当在所有可能的 $i$ 中选让最小胜率尽可能大的走最优。 现在考虑如何计算 $P(S, i, j)$。记 $S_1, S_2$ 分别为 $S$ 取走 $i, j$ 后的状态，$Q(S_1)$ 表示 $S_1$ 状态下 Alice 后手的胜率，有： $$ P(S, i, j) = \dfrac 1{a_i} Q(S_1) + \left(1 - \dfrac 1{a_i} \right) \left[\dfrac 1{a_j} P(S_2) + \left(1 - \dfrac 1{a_j} \right) P(S, i, j) \right] $$ 综上，状态数是 $O(3^n)$，转移是 $O(n^2)$，总时间复杂度 $O(3^n \cdot n^2)$。这个问题的启发点在于 $S$ 最终还可能回到 $S$，因此要枚举中间可能的其他状态，使转移式的待计算量只有 $S$ 本身。换句话说，是让所有计算量构成的顺序成为一个 DAG，不能形成环。 ===== D - 10億ゲーム ===== ==== 题目描述 ==== （交互题）Alice 和 Bob 各有一个 $10^9$ 的因子，从 Alice 开始轮流对各自的数 $x$ 进行下列一种变换： - $x \leftarrow \dfrac x2$ - $x \leftarrow \dfrac x5$ - $x \leftarrow \min(2x, 10^9)$ - $x \leftarrow \min(5x, 10^9)$ 变换后的数必须是整数，且和变换前的数要不同。记 Alice 和 Bob 各进行一次操作算一轮，寻找策略让 Alice 可以在至多 $35$ 轮内将自己的数变得与 Bob 的数相同。 ==== 解题思路 ==== 若数字可以分解为 $2^x 5^y$ 的形式，则实际相当于两人在 $[0, 9] \times [0, 9]$ 的格点上从初始点 $(x, y)$ 移动棋子，棋子每次能往上下左右四个方向移动一步，Alice 的目标是追上 Bob。 这是个经典问题：若一开始两人距离是奇数，则 Alice 先走到 $(9, 9)$，然后会与 Bob 所在位置形成一个矩形。若矩形不是正方形，则 Alice 就向下或向左沿着较长一点的那条边移动，使得矩形变成正方形；若矩形是正方形，则每次 Bob 移动后，Alice 都沿着能继续保持正方形的方向移动。显然，这样 Alice 最后一定能在至多 $35$ 轮内抓住 Bob。 注意本题中，利用操作 4 可以做到 $(7, 9) \to (9, 9)$ 的移动改变奇偶性，因此根据初始距离奇偶性确定要不要走这一步即可。 ===== E - ねこちゃんゲーム ===== ==== 题目描述 ==== 给定一棵 $n \leq 2 \times 10^5$ 个点的树，树上有 $m \leq 2 \times 10^5$ 只猫，第 $i$ 只猫在 $a_i$ 节点。每回合，Alice 和 Bob 轮流任选一只猫，将猫移动到其相邻的结点上，直到不能操作为止。对于猫 $i$，它不能移动到之前它呆过的节点，同时一个结点上可以有多只猫。 判断 Alice 作为先手是否必胜，若必胜给出第一步走法。 ==== 解题思路 ==== 显然这是一个组合游戏，只要求出猫猫以每个点为起点时对应的 SG 函数值即可。不妨假设已经以 $1$ 为根求出了每个点 $u$ 的 $\mathrm{SG}(u)$ 及其所有儿子节点 SG 函数值的出现次数 $\textit{cnt}_u$ 数组（用于求 $\mathrm{mex}$）。考虑换根 DP 正在处理 $u$ 为根的情况： **转移 1**：父亲节点有一个 $\mathrm{SG}(\textit{pa})$：直接更新 $\textit{cnt}_u$，然后 $O(\textit{siz}_u)$ 更新 $\mathrm{SG}(u)$。 **转移 2**：准备转移到儿子节点 $v$ 上：这里不能像上面一样 $O(\textit{siz}_u)$ 更新，否则总的更新复杂度 $O(\sum _{u=1}^n \textit{siz}_u^2)$ 是不对的。考虑删掉 $\mathrm{SG}(v)$ 对 $\mathrm{SG}(u)$ 的影响，发现只有删掉后 $\mathrm{SG}(v)$ 的出现次数为 $0$，且 $\mathrm{SG}(v) < \mathrm{SG}(u)$ 时，$u$ 的 SG 函数值才会变成 $\mathrm{SG}(v)$，否则不变。这样做就是 $O(1)$ 的。 综上，计算出所有点为起点时对应的 SG 函数值是 $O(n)$ 的。为了输出方案，还需要知道每个点为根时相邻节点的 SG 函数值。可以归纳地证明，为了让 SG 函数为 $i$，至少需要 $2^i$ 个节点，因此所有节点的 SG 函数值不超过 $\log_2 n \leq 17$，额外记录一下这 $O(\log n)$ 个信息即可。 总时间复杂度 $O(n \log n)$。