2026 ICPC 网络赛出题记

· · 生活·游记

2026 ICPC 网络赛出题记

本文同步发表于知乎和博客园，本文为 第四届你要魔怔杯鲜花大赛！！1 参赛作品。

造题阶段首先就被怎么写题面给困住了，当时同时也有在打每周四场多校。大概连续想了两个晚上终于敲定了一版合理的中文题面，而且感觉“非常有现实意义”。然后跟 deepseek 协作完成了英文题面。这个时候是 $8$ 月初。 然后要写 std。由于我对 AI 的使用还停留在只会用 AI 翻译和查语法（甚至不知道 deepseek 开深度思考更聪明所以从来不开），所以到目前为止的算法正确性证明都是脑内自证的。写 std 后与暴力对拍，发现了一个 hack 数据，把我的做法 hack 了，并发现很难修正。于是我打算直接修改数据限制，使得在数据限制下我的算法是正确的（也是我脑内证明的，但这一次证明比较详细）。在给组题的人说了之后我就开始写满足限制的造数据程序。事实上，需要造满足限制的数据相当于重写一遍这道题，而由于我对 AI 使用的缺陷导致我造数据程序都是手写的。经过一下午搏斗后造了好几组随机数据。然后自己脑补了一些特殊情况，造了几组 hack 数据。由于这道题不是一个数据里塞多组数据，所以我还非常有创造地把我手造的 $10$ 种左右易错的小数据融合到一组数据里。感觉数据强度足够高了。 过了不久就是校内验题环节了。校内大概有一半的队伍通过了我的这道题，且随机询问了一些人的意见对于这道题没有意见。我再把这道题的题面看了很多遍，改了几个小词。然后愉快地坐上了回乡的航班。这个时候是 $8$ 月 $22$ 号。 到家一天后，在跟朋友逛街的过程中同学给我发了一道 CF 题。我点开了这道 CF 题，发现跟我出的那道题很像。准确来说，这道 CF 题是我出的题 $K=1$ 的版本，而我出的题 $K\leq N$。我发现这道 CF 题是 $5$ 年前的，我没做过也没见过，但是做过的人极多。虽然我出的题严格来说不完全跟这道题一样，但思路相似度极高，如果做过这道题几乎可以再多想两步就能会做我出的题，而对于没做过这道题的人可能要难一个档次（虽然即使是这样也不难）。但是在经过 $1$ 分钟的思考后，我给组题人说了把这道题毙掉的打算。当晚的晚饭很好吃，朋友也很高兴，我却吃不下了，草草地回了家。这个时候是 $8$ 月 $24$ 号。 由于我的另外一个 idea 已经在前面的比赛被用掉了，所以我得从头开始想 idea。我在床上躺着彻夜未眠，毫无头绪。每想到一个有趣的 idea，我就起床查原题机，然后发现被出过了。还有一个没被出过的 idea，我不会做，让 deepseek 帮我想，他想不出来。 我熬到早上终于熬不动了，开始昏迷，昏迷到晚上又醒了，开始继续想 idea。我想到一个感觉很基础的操作“折叠”，发现在树上把直径折叠起来这个操作很自然，而且折叠次数虽然是 O(N) 的但是直径长度只有 $O(\sqrt{N})$ 类，只需要将一类折叠操作一轮 $O(N)$ 同时执行，即可做到 $O(N\sqrt{N})$。我毛估估地想了想感觉任意折叠方法的折叠次数是相同的，所以我题面问的是求折叠次数最大值，其实是需要做题人意识到折叠顺序不影响答案。于是我去原题机搜，发现压根没有类似的题目，完全没有人能想到树的直径是能折叠的！于是我在凌晨把这个 idea 发给了组题人。然后睡着了。 醒来之后发现组题人已经看完这个 idea 了，并且他感觉有点不对劲。经过讨论之后我才意识到，折叠方式的不同会导致树不同构，所以折叠次数并不一定是固定的。而我用的 deepseek 完全没有能力发现这个问题也无法解决这个问题。组题人让 chatgpt 跑一组不同折叠方式导致折叠次数不同的构造方案出来，而我则在思考如果真有反例我该怎么办？我提出了如果有反例就把这道题变成钦定操作顺序，这样就是一道纯粹的优化模拟题了（虽然我认为也较为有趣），但是出于对网络赛题目质量的高标准要求，我跟组题人都觉得这题不足以上网络赛。过了几十分钟，chatgpt 并没有跑出反例，这时我意识到可能折叠次数真是固定的，但我完全无法证明这个结论，于是又让组题人用 chatgpt 跑证明。而我被家长带出去吃饭。吃完饭回来，天已经黑了，chatgpt 跑了几个小时竟然真的跑出来一个形式化证明。而我又花了一晚上想清楚了这个证明，并且用自己的语言把这个证明说了一遍，虽然极其不形式化，但是非常对。这个时候我认为这道题的 idea 已经足够优秀了，于是我开始造题。这个时候是 $8$ 月 $26$ 号。 我又通宵了一晚上，写了题面，暴力，正解；写了 $8$ 版造数据程序，造不同类型的数据；上传到 polygon，让 AI 给我写了 validator。剩余的时间我又思考了一下这道题的证明，确实没问题。 我的 7 天暑假在想 idea 和造题中结束了。我又坐飞机回到了学校。 后来又请了一些人来验题，对我这道题提出了一些宝贵的意见。由于我造数据是人脑构造极限数据，导致我的极限数据不够极限，验题人发现了这个问题，并让 chatgpt 生成了一组能把所有代码全部卡成 TLE 的数据。但我认为这题的时限不能开太高，所以我选择调小数据范围。这也就意味着所有数据全部都要重新造，不过由于我留了造数据程序，所以倒也不难，只花了一下午就重造好了。新增一个极限数据。在重新敲定时限的过程中，鉴于 $O(N\sqrt{N} \log N)$ 做法跟 $O(N\sqrt{N})$ 做法没有本质区别，所以我时限给得较为宽松，多一个 $\log$ 也能通过。 同时，验题人的 chatgpt 验题的时候发现了这道题有一个更加精妙的结论，可以直接把这道题的复杂度优化到 $O(N\log N)$，让我叹为观止。但是由于这道题定位是中档题，所以并没有加强，这也是我觉得比较可惜的一点。 后续验题中还对于题面做了一些修改，并且增加了样例解释。在上传题目截止日期的时候我还是不放心，又加了两组数据。我把题面看了又看，虽然过于形式化确实丧失了部分简洁性，但是定义会更准确。后面发生的事就不是我能控制的了，尽人事，听天命。这个时候是 $9$ 月 $9$ 号，离比赛开始还有 $3$ 天。 后面几天，每天早上 $9$ 点到下午 $5$ 点在机房做题，不想做题的时候我就会重新证明一次这道题。终于到了 $9$ 月 $12$ 号，网络赛总算是开始了。我全程守着答疑区和榜单，在比赛进程过半时候就发现了异常。我出的题定位本来是中档题，但在 $2$ 小时后才有第一个队通过，甚至封榜前通过队伍数量是个位数。跟这道题处境类似的还有 H 题，尽管 H 题出题人已经在标题后加了 “easy version”，也无法阻止歪榜的发生。直到最后，也只有清北的 $16$ 支队伍通过了我的这道题。尽管如此，我对这场比赛依然保持乐观态度。 实事求是地说，这场网络赛的少部分题目数据确实弱了；还有一两道题确实卡常；以及中档题较多导致大部分选手打起来比较坐牢。这场比赛确实有一些需要改进的地方。 但是我不认为这场比赛区分度很低。$4$ 题垫底校排 $170$，也就是只需要有做得起 $4$ 道题的水平就足够出线，而前 $4$ 道题的 gap 也是合理的，D 题刚好能区分出出线和不能出线的队伍。$4$ 题首校排 $57$，而从第 $5$ 题到第 $9$ 题都属于中档题的范畴，考虑到校排前 $50$ 是一个需要区分的排名且校排前 $50$ 一般意味着有金牌能力，所以应当在第 $5$ 题到第 $9$ 题这 $5$ 道银牌中到金牌且考察方向各不相同的题目里至少做出一道才能进校排前 $50$，所以反而这场比赛对这部分队伍的区分度其实极高。 当然也有区分度较低的分段，可能会影响校内自行排名，这也是以后需要克服的问题，比如低估了计算几何的难度且 C 题卡常导致 $9$ 题以后的区分度较低，且签到题较少使得校排 $170$ 以后的队伍区分度也较低。 以及大部分人 K 题所谓的“卡常”都是复杂度 $O(N^2\log N)$ 及以上的，而这道题本来就不允许带这个 $\log$，所以 K 题只有复杂度严格 $O(N^2+Q\log N)$ 且 TLE 的队伍才能说是被“卡常”了。反而 K 题或许有人带 $\log$ 过了，可能是常数较小，这个倒可能是一个问题。我想可能说 K 题卡常的人的意思其实觉得 K 题不该卡这个 $\log$，这个就仁者见仁智者见智了。 赛后对于比赛的负面评价比想象中的要多，有问题的地方该骂确实得骂。但是我无法理解为什么我出的那道题会有很多 downvote。而且看到群里满屏 BadProblemF 也确实不好受。因为大部分人完全没有做过甚至看过这道题就给我的题点踩以及在群里说是 BadProblem。还有人在各种地方发表了对出题人的各种攻击。 事实上本场比赛有超过 $5$ 道质量不低且难度不高的题由于被查重而被毙掉，所有题目平均 polygon 版本也有 $10$ 次以上。出题验题改题的工作从 $7$ 月一直进行到比赛前一天。不可否认仍然有少量题目数据还是弱了，但是大部分题目都是没什么可以挑剔的好题。或许最大的问题反而是简单题出少了让很多人打得不爽，毕竟第 $3$ 简单的题都涉及到要优化掉一个 $\log$ 这种较为考验基本功的考法。 几个月前在一个小出题群里，我说，我的愿望是出一道能够成为经典的题。它足够优雅，足够简洁。 现在看来，我确实出了出来这样一道题，还被点了好多踩。