关于 一些算法 “应该”或 “不应该” 卡的思考

· · 个人记录

刚才看到洛谷管理群在讨论字符串哈希模板是否应该接受自然溢出题解的问题，当然这同时也是一个争论已久的问题。这篇文章希望提供一种可能更“普适”的新角度。

“算法” 的同一性到底应该如何定义？当我们提到“最短路算法”时，这个词汇指代解决特定问题的一整类方法；但若换一个语境，我们又不会认为 Dijkstra 和 Bellman-Ford 是同一种算法。这是自然语言在范围改变时产生的含义变化。

那么如果这个范围缩到无限小呢？难道我们应该认为：每一份不同的代码，都代表一种不同的算法吗？作为代码编写者，这个定义也许是合理的；但如果站在出题人的角度，OI 评测的基本原则是黑盒，所以我们无法获得选手的具体代码，此时我们能预先（造数据时）区分的只有“代码的运行特性”，也即 -- 两份代码属于不同”算法“，当且仅当它们可以在黑盒中通过绝对精确的时间/空间/运算次数测量加以区分。

由此我们引出一个定义：“算法等价类”，它们是出题人所不能够预先区分的极大集合族。例如：在代码最后加上一行注释不会改变其所处的等价类，因为这不会对代码行为造成任何改变；在代码最前面加上一个 assert(1+1==2) 会改变其所处的等价类，因为这份代码多进行了一次运算和一次判断操作；改变随机数生成器的种子不会改变其所处的等价类，因为在 WRM 下这不会对运算特性造成任何改变。

此时给出我的主张 -- 在同一个“算法等价类”中，不应该进行感性或经验性的区分（事实上等价于不能进行区分，因为定义已经说明了它们不可能被理性地区分）。

例子很好举。比如你不应该盲猜选手种子是 114514 然后进行狙击。这一诉求的正当性可以轻易由 我们对竞赛公平性的共识 所导出 -- 不同国家，不同地区，不同学校的学生在知道这个梗的差异度上都是不同的，因此这一行为显然带来了 基于专业知识之外的（甚至有可能是地域性或种族性的），毫无意义的不公。

必须声明的一点是，以上主张不“禁止”对任何算法等价类的 hack 尝试，只是反对在同一等价类内部的区分。举个例子，你要卡随机种子，可以 -- 请你在种子的可能范围内随机生成一个去卡（也就是说，卡中的概率是 2^{-64}，这里不是无穷小，因为如果你使用 int128 作为种子就会改变运算特性）。

那么现在回到最初的那个问题 -- 为什么按照这个定义卡自然溢出是正当的？因为自然溢出和其它哈希并不处于一个算法等价类中（它少做了取模，不然也不会有这么多人用它了）。更重要的是，自然溢出所在的等价类的模数只有它自己。所以这个时候，你对这个等价类去卡，卡中概率就是 1/1 了。

一种常见的反驳可能认为“自然溢出和普通哈希差的不多”。从理论上前文定义已经很明晰了--它们就是可以被预先区分。而从更直观的角度，存在大量的错误解法和正解的编辑距离都是极小的，这也没有影响它们被全部干掉。