标题不能为空

command_block · 2023-07-28 11:58:11 · 个人记录

标题党。

NOI2023 的闭幕式上，数百名选手领走了他们的牌子，又一个赛季结束了。

往年这个时候，LA 群应该是怎样一幅光景？可谓是：

队爷互膜刷满屏，场外后浪口胡金，各省网红齐面基，老年选手叹退役

可今年这一切都没有发生。或者说，发生得相对隐蔽。因为一场关于 OI 现状、改革和未来的大讨论正在进行。

（已经进行完毕了，现在群里到处是面基照片）

如何设计 OI 赛事的规则?

现在是，幻想时间！

假设你拥有上帝视角，你会举办怎样的 OI 赛事呢？

• 信息学研究什么？ 设计算法，解决问题。

现在要为这门学科举办竞赛，可以直接还原其研究目的。

• 方案 A：给出问题，选手用自然语言描述算法。根据描述的正确性/完备性、算法的时空复杂度来评分。（等同于写论文）

大家都知道，这种方案从来没被采用过，原因有三。

• 原因一：竞赛并不是 1:1 还原学术研究，它兼有知识普及和人才选拔的双重任务，为此，我们还要考察选手的 代码实现能力 和 对基础算法的掌握。

  纯纯口胡的【方案 A】用一句“Tarjan 求强联通分量，复杂度 O(n+m)”带过了很多事。选手可以根本不学/不会写 Tarjan，只记住它的用途和名称。（当然，搞学术的话，没人细究你到底懂不懂 Tarjan，但竞赛不行）

• 原因二：算法的细节可能非常多，要用自然语言完备描述，还不如直接写代码。比如很多数据结构题。（这部分由竞赛题目的特性导致，为了选拔效果，需要命制细节复杂的问题）

• 原因三：没有充足的工作人员来为答卷评分。

于是你抛弃了原教旨主义，机械飞升！

• 方案 B：选手根据自己设计的算法写出代码，使用机器对代码进行评测。

这一举解决了上述所有问题，还带来两个额外的好处。

• 机器评分的客观性避免了主观误差，提高公平性。

• 机器评分的高效性让大型线上比赛的举办成为可能，扩展了 OI 的生态。

然而，机器评测也带来了许多新的缺陷，这里挑两个重要的讲讲。

• 缺陷一：选手不必为自己的代码提供证明。

  • 选手 A 随手猜结论过了题，选手 B 对问题进行了细致的分析和讨论，最终推导出结论，也过了题。显然，选手 B 展现出了更高的水平，但两人的实际得分相同。

  这问题稍稍有些棘手。目前 OI 主流的“实用主义”价值观宣称“能跑就行，管啥证明”，但这真的合理吗？

  让我们把目光转到 P3243 [HNOI2015] 菜肴制作，这是一道绿题，可以看到，在题解和讨论区中，有不少初学者称其为“拓扑排序模板题”，他们这样描述自己的思路：

  首先自然想到贪心求字典序最小的拓扑序，发现存在反例，那么反过来，让最大的数优先排在后面，就可以了。

  显然，这样写的同学并没有完全理解算法的正确性，更谈不上将“字典拓扑原理”灵活运用。他们只凭着“代码写个拓扑排序”就轻易地判定了这道题的难度，或认为此题是“偏题、怪题、罕见题”，将其排斥在主流之外，这也是 CNOI 长期以来的一个弊病。（不过随着 AtCoder 的推广，这种误读在逐渐减少）

• 缺陷二：容错率低，评分梯度差。

  这是最大的问题。

  按照【方案 B】的思路，为了避免“选手写论文”，我们改而让选手写代码，用机器评测。代码其实是论文的“等效”替代，把主观题变成了填空题。

  想象这样一种情形：选手把代码写在纸上，收卷后抄到机器中评测，只有一次机会。

  这听起来十分荒谬，但我们静下心来想想这为啥荒谬。为什么论文可以写在纸上，代码就不行呢？

  因为机器具有客观性，不会像人那样变通，代码的语法要求非常严格，稍有不慎就会 CE。选手必须小心翼翼，让自己的代码处处能过编译，并为此消耗大量的精力，这不符合我们考察的初衷。换句话说，不借助工具，保证自己代码的每个细节都能过编译，不是选手的义务，也不是 OI 的教育目的。这是大家都公认的事。

  （当然，这不代表没人可以做到，比如 yjq 就有记事本过题的动人事迹）

  所以，我们会给选手发一台机器和编译软件（这属于题目之外的提示），他们可以多次编译自己的代码，以排除语法错误，顺便测试运行情况。于是就有了第一种比赛制度：

  • 方案 B-1（OI 赛制）：只提供机器和编译软件。（通常有小样例）

  然而，问题并没有完全解决，还可能有以下情况发生：

  • 情况一：思路全都正确，某个地方把变量名写错了，喜提 0 分。

  • 情况二：思路只有一个小细节错了，喜提 0 分。

  • 情况三：整个题分为四个步骤，前三个步骤都会了，最后一个不会，喜提 0 分。

  在这三个例子中，选手都有大小不等的错误，故不应获得满分。人工改卷的【方案 A】会酌情保留一些分数，但【方案 B】会直接给出 0 分，选手为较小的错误付出了沉重代价，这不符合我们的设想。为了缓解这一问题，有两种比赛制度可选：

  • 方案 B-2（黑盒 IOI 赛制）：提供一个即时响应的评测系统，可随时提交，测得的结果即为最终结果。

  • 方案 B-3（白盒 IOI 赛制）：提供充分多的、可见的测试数据。选手不仅能即时判断代码的正误，还能得到合适的 hack 样例。

  这其实是一种曲线救国的方法。犯下小错误的代码仍然无法得分，但即时评测的提示给选手提供了多次检查和试错的机会。它没有让犯错的（过高的）惩罚变低，而是作为一种代偿，将修正小错误的成本变低了。

  这增多了题目之外的提示，所以会产生副作用：【缺陷一】的负面影响被放大了。在 OI 赛制中，猜结论只有一次机会，而 IOI 允许猜测多次，在白盒 IOI 中甚至可以通过观察样例来猜结论（实践表明，这是很强的辅助）。

  此外，IOI 模式只能对（再努努力就过题的）情况一/二生效，对情况三则无能为力。

机器评测的两大理论缺陷已经介绍完毕。别忘了，以上讨论是在“数据、评测资源无限”的理想情况下进行的，现在来考虑现实情形。

• 现实障碍一：数据范围并非充分大，不能正确区分算法的时空复杂度。

  • 同复杂度的两份代码，可能只有常数小的通过。（卡常）

  • 复杂度差的代码，可能因为常数小跑得更快。（比如有些题 O(n\log^2n) 比 O(n\log n) 显著更快）

  这倒不是一个致命的问题。许多选手本着“抓住老鼠就是好猫”的实用主义精神，提出“跑得快就是好算法”，乃至“卡常就是 OI 的一部分，不服不要玩”等理论。

  如果有一个跑不过 O(n^2) 的 \tilde O(n\sqrt{n}) 做法，大家会认为没什么意义，而 \tilde O(n) 的 Min_25 筛大家用得很爽。

  虽然这有些偏离我们搞学术的初心，但也可以接受。

  为什么处理【缺陷一】时不接受实用主义，处理常数问题时接受？

  究其根本，“写出常数优秀的代码”本身是一项有价值的能力，“跑得快就是好算法”对小常数选手有利，（至少在某种维度上）属于正向选拔。而【缺陷一】只对猜结论选手有利，不会做的选手（没分）和严谨证明的选手（消耗更多时间）都吃了亏，这称不上是正向选拔。

• 现实障碍二：数据强度不够。

  • 个乱搞做法随机数据跑得很快，由于出题人没有对着卡，它过题了。

  在 IOI 赛制中，后果更加严重。选手在 OI 赛制中写乱搞，还可能自我怀疑，和空气斗智斗勇，而 IOI 过了就是过了，毫无后顾之忧。

  • IOI 赛制下，某个随机算法提交很多次，靠运气过题。

  对于第二条，分别设立 pretest 和 systemtest 就可以解决。

  第一条有些棘手，出题人先手造数据，难以预料选手会写什么乱搞。出题团队只能自己想一些乱搞，并卡掉他们，这对于写乱搞的人来说等于随机刀人，而且概率不明。

• 现实障碍三：评测资源不足。

  考过 APIO 的都知道我说啥。要是真弄成了 IOI，你百分百放心吗？

总结：

OI 赛事的举办依赖于机器黑盒评测，后者的绝对客观性、绝对实用主义带来了种种弊端，具体开列如下：

• ① 容错率低

• ② 评分梯度差

• ③ 选手不必为自己的代码提供证明

• ④ 数据强度不够

• ⑤ 卡常

• ⑥ 评测系统不完全可靠

当然，与此同时，机器评测还具有一系列优点，或者说相比之下人工改卷有一系列缺点（主观性强，效率低下，可能误判或被欺骗）。

机器和人工这两种测试方法都有各自的优缺点，本身并无高下之分。但要注意到，大多数考试（尤其是高考），都采取人工改卷的模式，大家也习惯于认同这一模式，那么人工模式自然成为了评分伦理的本位。

为什么选手会破防？为什么某道题目受到批评？

“结论哥直接秒题，我 2h 只有 15，果然猜出来就进队啊，全靠猜结论区分……”

“大样例没有一样，一堆人正解挂成 20，随机送一半人离场是吧？”

发生这种情况，选手是直接受害者，出题人被指认为直接责任人，然而究其根本，这是机器评测和赛制的固有缺陷在某道题目中暴露出来的结果，现有评测制度的缺陷才是最终原因。

所以说，无论是选手还是出题人，都要有更强的同情心，要意识到我们是在一个有许多缺陷的系统中举办比赛。有一些受到批评的题目，如果以纯学术讨论的眼光来看，质量上没有任何问题，但它天生不适合在现有的评测体系下运行。

我对正式比赛以及网络赛的出题人提出以下建议：

不要让您的题目触发体系的弊端。

• ④ 数据强度不够

  • 方案一：别出能乱搞的题。数数！

  • 方案二：如果出了能乱搞的题（字符串数据结构之类），把问题规约到一个基本形态，卡满它。

  （规约到 01 矩阵乘法，你可以确信不会有乱搞做法）

  （如果 std 需要利用信息的某种性质，你可以假设信息没有这个性质，然后卡满，如果要突破这个界就必须利用此性质）

• ③ 选手不必为自己的代码提供证明

  别出纯结论题。已经有 idea 了咋办？卖掉吧，明哲保身。

• ② 评分梯度差

  别出 ad-hoc 题和多合一，除非是压轴题。

• ① 容错率低

  提供靠谱的大样例。

说实在的，其实选手和出题人的利益有很大相关性……只要选手不破防出题人会不会风评被害了。何必互相为难呢？

关于组题

希望正式比赛的题源能越来越多，只要题源充足，一切都能好起来的。