7 月 17 日闲话

· · 个人记录

今天来聊聊洛谷月赛的前期题。

实际上洛谷月赛的定位相比其他很多赛事是尴尬的。洛谷的一场比赛试图要涵盖从入门阶段的题目，到专门让国内顶尖选手去挑战的题目。

这个看似和 CF 类似实际又不一样。虽然洛谷也提供了 Div.1（提高-省选） 和 Div. 2（入门-提高） 的配置，但是每个 Div 只有 4 题，这与 CF 的 6 题是不一样的。CF 的 6 题意味着其每个题之间的 difficulty gap 能比洛谷月赛更为平和。若难度是均匀分布的话，CF 的 difficulty gap 是洛谷月赛的 60% 吧。（现实情况下不太会这样，所以这是个暴论）

有人说洛谷月赛的参赛者其实分数都是一层一层的大台阶，其实也有一定程度是这个问题，偏大的 difficulty gap 会使得哪怕 A 比 B 强上一些，A 也不一定能往后多做一个题或者取得一个可观的部分分去取得一个显著更好的成绩。当然这与洛谷采取的 IOI 赛制也是有关系的，像 CF 在 Final Standing 上其实选手同分的情况是不多见的。

一方面这让选手的分数是集中在各个分数段上，另外一方面这其实对洛谷月赛的出题人增加了压力。出中等题或者难题，洛谷月赛的出题人都是会的。但是怎么出简单题？怎么出好简单题？这两个便是大的问题。特别是因为洛谷月赛每次能够放出去的题目是 6 个题，每个人都希望自己的有趣的 idea 被展示出来，这使得对前期题的看重程度是弱的。

这里需要注意的是，有趣基本是与有一定思维量画等号的。问题在于，洛谷的用户的高度下沉，使得其实有较多选手的思维能力是弱的，只会不动脑子的模板题或者常见的套路。对于他们而言，如果思维量就一小些那还是可以做出来的，但是部分试题对思维量要求较高，如果放在很前面的话容易引起很多选手的罚坐。

在洛谷主体用户是只能去做 div2，特别是 div2 的 AB 两题的情况下，往 div2 前期放太多对思维有挑战的题目是对参赛选手的一种折磨。这里就特别需要指出的就是 adhoc 题前往不要往前期放。 简单的 adhoc 题容易出现负区分度，因为想到其做法的随机性过强了。代表的反例是 Codeforces Round796 的 Div 2C，它真的不算难，但是就是造成很多选手卡这个题上。

这样一来我的态度是明确的：Div2 AB 最好出一些平和的题目，难度为洛谷的红黄或者橙黄，对标的是普及组第 1.5 题和第 3 题左右的难度。这样，哪怕是入门的选手也能做一个题，而有普及一等的选手可以做两个题，大部分用户就不会觉得毫无体验了。

那么现在的洛谷月赛都是长什么样呢？以下的题目都节选自最近几场洛谷月赛的 2B。

定义两种操作：
操作 1：将一个正整数 x 变为 x+\mathrm{lowbit}(x)。
操作 2：将一个正整数 x 变为 x+\mathrm{highbit}(x)。
现给定一个操作序列和 q 次询问，每次询问包含 3 个正整数 l,r,x，表示将 x 从左到右依次执行 l\sim r 的操作，请输出 x 的值，由于答案可能很大，请输出答案对 10^9+7 取模的值。——洛谷一月月赛 II

已知数列 f 满足 f_n=a_nf_{n-1}+b_n\ (n\ge 1)。问是否存在非负整数 f_0，使得 \forall 1\le i\le k，f_i 为质数 p_i 的倍数。——洛谷二月月赛 II/EZEC R11

给定两个序列 a_1 , a_2 ,\cdots, a_n，b_1 , b_2 ,\cdots, b_m 和 k。可以删除 0 或 1 个 a_i，使得 (\sum \limits_{j=1}^{b_i}a_j)\bmod k=0 的 i 最大。求这个最大值。——洛谷三月普及组月赛/WdOI R5（OI 赛制）

有一个长度为 n（1\le n\le 10^5）的整数数组 a_1,a_2,\dots,a_n，有前缀异或数组 p_i=a_1\oplus a_2\oplus\dots\oplus a_i 以及后缀异或数组 s_i=a_i\oplus a_{i+1}\oplus\dots\oplus a_n。一共将 p 和 s 的 n 个元素换成 -1。给定当前的 p 与 s 数组，请恢复任意一组可能为原数组的 a_1,a_2,\dots,a_n。——洛谷四月月赛 I/MCOI R8

对于 n \in \mathbb{Z_{\ge 2}}，设 g(n) 为 n 的小于 n 的最大约数，如 g(7) = 1, g(12) = 6。
定义 f(n) = n + g(n)。记 f^{(0)}(n)=n，且对 m \in \mathbb{Z_{\ge 0}} 有 f^{(m+1)}(n)=f(f^{(m)}(n))。
多次询问，每次询问给定正整数 n,k，求最小的自然数 m_0，使得对于任意 m \ge m_0，均有 f^{(m)}(n) \mid f^{(m+k)}(n)。
若不存在这样的 m_0，则令 m_0=-1。 —— 洛谷四月月赛 II/CoE IV

不是说这些题目不好，而是说它们的位置不对。如果打了两年洛谷月赛的人，应该知道在两年前，这种题目应该更倾向于放在 Div.2 C 的位置（对于普及组月赛而言则是倾向于第三题），而不应该是 Div.2 B 的位置。腾出来的一个题目可以让前期题的难度曲线变得更平滑。这样的分配可以让更多的用户参与月赛其中。实际上，我挑选的这些题目在赛时的 AC 率（AC 人数/整场比赛提交过并不会 CE 的代码的人数）都是不足 10% 的。

当然还有个更大的反面例子：

给定一个正整数 n 和自然数序列 a_1,a_2,\cdots,a_n。你需要对每一个 0\le S\le 2^n-1，求出数 S 的“权值”。一个数 S 的权值 v(S) 的计算方式是：把它写成二进制，如果它从低到高第 x 位为 1，就把答案异或上 a_x。把所有 v(S) 求出来之后，把答案分别乘上对应的 S，然后异或起来，取模 2^{64}。

这个并不是题目 idea 不行。实际上 idea 还是可以的，但是其展现的形式会长得很怪。我真的觉得，如果不是一个每天都在研究洛谷评测机运行速度的人，真的想出来也不会去写 O(2^n) 的做法（看着就跑不过去，但是我某次闲的没事干测洛谷评测机，知道其上限是 1s 可以跑 1.2e9 次 ull 相乘自然溢出）。一个不懂 L2 Cache 的用户，也会惊讶于为什么他拆了两个 65536 大小的数组存高低位能过。这种负区分度的题目还是别在洛谷月赛出现为好。

两个正面教材如下，其中第一个是对偏易的比赛，第二个是对难度中等的比赛。其赛时的 AC 率分别为 50% 和 30%：

有一个 \frac{0}{x} 的分数。重复以下步骤直到这个分数为 1：分子 +1；如果这个分数可以约分，约分到最简形式。问对于 \forall i \in [1,n] 的步骤操作次数最大值。——洛谷五月月赛 I/JROI-4

给定长度为 n 的序列 a 和常数 c。构造点数为 n 的有向完全图 G 使得边 i\to j（i\neq j）的长度为 a_i-2a_j+c，保证所有边权非负。接下来给出 q 次询问，每次给出一个点集，试找出图 G 的一条最短的简单路径，满足其经过点集中所有点，并输出它的长度。——洛谷五月月赛 II/WdOI R6

但是上述所述的，又是建立在洛谷 Div.1 难度已经趋向于饱和的情况下。这个情况下，Div.2 的前期包括中期题目的难度下调，并不会引起 Div.1 的难度的整体崩塌。实际上洛谷月赛的 Div.1 大多数情况下是难度足够的甚至有些太难了，因为大部分现在的月赛 Div.1 ，一般人类难以取得 300 分。这个时候，如果通过平衡 Div.2 A-C 的试题难度，进而下调一下 Div.1 前期题难度，这也会增加较高水平的用户参与 Div.1 的兴趣，而不是在 Div.2 和水平更低一级的用户抢首杀。

当然这一切的问题还是在于洛谷尝试使用 6 个题去涵盖入门-神题的范畴，哪怕多两个题问题的窘迫性也可以减少很多。但是从目前的状况来看，我还是支持月赛的前期亲民一些的。

附带 kkk 的月赛要求，分别是 div.2A 通过率 65% 和 div.2B 通过率 30%，允许稍微低一些，但是像今天这种肯定说是不行的。