随笔选辑 - 我对 OI 的想象
返回目录
作于 2023.4。
我对 OI 的想象
尝试稍微完善一下我设想中的 OI 的理想状态……现实中官方比赛肯定不能实现，但我觉得如果是我出的小比赛，可以做这样的试点。
（不能真正实现的主要原因是，很多人（身边采访）觉得这不符合 OI 的特点，事实上大部分意见在可行性上我并不觉得存在什么问题）
下述内容一个核心原则是：在限制选手的时间和参考资料的情况下，我们尽可能地减少选手为编写代码及相关工作（例如调试代码）所需要做的努力。
1
先说一个比较脱离目前现实的，但我认为恰恰是未来最有可能（至少在网络比赛中）发生的事情：选手将可以使用 AI 辅助编写代码。
算法竞赛中其实还是有许多代码是重复度比较高的，可以用（未来的）AI 编写的代码应该是不少的，这可以减少很多选手敲代码的代价。
2
在目前的正式 OI 比赛中，选手们会有或多或少的挂分，同时选手为了保证尽可能少的挂分会花更多的努力在一道已经完成的题目上。例如他们会写对拍，我认为这是毫无意义的。因此，必须使用 IOI 赛制。
3.1
即使是 IOI 赛制，也总是有调不出来的代码，更不用说许多 IOI 赛制的赛题甚至不提供较大的样例，这使得调试变得困难，许多时候选手需要自己生成数据并写暴力来发现错误点。这会浪费大量的时间，又回到了对拍的问题上，然而事实上选手已经知道了一组错误的数据——那就是测试数据。因此，在错误提交后需要提供给选手错误的测试数据内容。 注意这里说的不是像 CF 那样只给你看前几行，而是应该提供完整数据。
3.1.1
那么大家有一个显而易见的疑问：既然选手可以看到出错的数据，那么如何避免打表过题？
答案是简单的：我们评价一个代码正确与否，根本的标准是它能否通过全部的符合题目条件的数据。只是因为我们没有手段验证所有数据，才只能从全数据集中挑选一些作为测试数据。那么只要每次测试数据都不同，就可以避免打表过题了。因此，在 3.1 的假设上，每次测试的测试数据应当是不同的，由某个数据生成器即时生成。
至于如何防止选手通过观察数据特性来找到数据生成器（gen）的特点，那就是出题人的任务了。事实上，仅 3.1 这一点就对出题人提出了极大的挑战。
3.2
为了防止选手调不出代码，我们还有另一种方法。
那就是 提供数据生成器（gen）以及标程（std）的可执行文件。 这帮选手省去了写数据生成器和写暴力的时间。
当然，出题人需要做一些技术性处理，例如标程的运行时间和空间需要进行混淆，以防选手以此测定标程的效率。
被抛弃的想法
有一种最强调 OI 纯粹性的想法：那就是选手可以形式化地描述自己的算法，并对算法的正确性进行形式化的证明。
但这是不太可行的，因为我目前看来，形式化描述并证明算法远比写一个代码要困难得多，这就不符合我们的根本原则了。事实上上面所说的内容丝毫没有强调所谓 “OI 的纯粹性”（这个说法一般是指，对错都由电脑判定，不是人来批阅的），而是把它当成一个可以牺牲之以换取选手便利的东西。
另一件事情是：是否允许选手直接使用某些模板或者自己以前写过的代码？我认为如果允许的话将破坏竞赛的公平性，并导致进一步的内卷，因此觉得还是不要允许为好。
一些说明
我们有如下主要观点：
想要避免某个人做某件事，只需要让他做这件事的代价大于不做这件事得到相同结果的代价大即可。如果你要问在 3.2 中如何避免选手反编译 gen 和 std，那么其实很简单，只要让他在有限的时间和资源内不能够反编译出来，或反编译的代价和难度大于做题的代价和难度即可，这应该是不难办到的。
也许有人觉得，提供某些数据的标准答案甚至于提供数据本身会给选手额外信息。但我的观点是这些信息是选手应该获得的。有人可能要问，那些可以打表的题怎么办，输入只有一个数的题怎么办。我觉得有两种解决方法：一种就是不要出这个题了；还有一种是出成提交答案题。
上面这些想法的出发点就是：一部分的写代码的工作和调代码的工作对于 OI 来说本是无意义的劳动。 事实上，写代码这件事本身就是一种妥协而不是 OI 的必然。这一点是有人反对的。有人说如果这样的话 OI 就变得和 MO 类似了。但我想不是这样，我们恰恰希望取长补短：MO 相对 OI 的长处是会了一个题之后写下解题方法相对简单，短处是由人来批卷，并且选手可能需要更多地考虑写法等方面的问题；OI 相对 MO 的长处是机器批阅，对错比较分明，短处是在会一道题后还需要付出大量的努力来编写代码。
事实上，在以上背景下，我不反对出代码量较大的题，但在现在的 OI 背景下我绝对反对。只有有了这种能够保证选手有可能快速写/调出长代码的机制，才使得选手赛场上尝试码量题成为可能。
出题人是一个服务业。出题人应该尽可能地为选手着想。例如，出题人因为数据制造的粗糙等原因拒绝提供大样例，是出题人的懒惰。