开学的几周因为沉迷摆烂没找组织约人组队。新生赛打完后才发现榜前大佬很多都组好了,只有黄巨愿意跟我预约组明年的队。已经放弃了这个赛季的 ICPC 了。南京赛前几周,黄巨打女生赛用光了参赛次数,于是她的队友 Destiny 和张神找了我,我终于能够参加今年的 ICPC 了。
Destiny 为在合肥站拿了银首心有不甘,卧薪尝胆南京拿金势在必得。赛前三天 Destiny 把我拉到计院打练习赛(张神怕阳没来),在爆切三题后又再随手切掉一道我调了两个小时的题,带领全队三小时夺金。他欣慰地看着榜单,雄心勃勃地给我画大饼。赛前一天我们三人又聚了一下,两人给我这个一次 XCPC 都没打过的萌新科普知识,展示监考系统使用方法。
12 月 18 日上午 11 时,比赛开始。我上来就看最后一题 M,一眼丁真 “\/” 形结点就是要挖洞的地方,但是张神指出了水平边的 hack,我只能继续冥思苦想。然后 Destiny 和张神就切掉了 I 和 G。之后我就占用电脑,尝试用叉积判凸+左右找第一个非水平边,写了一个丑陋的 $O(n^2)$ 过掉了 M(尽管实现的精细点也可以达到线性复杂度,但这题没卡 $O(n^2)$ 我就懒得写了)。此时才开赛一小时,Destiny 表示我们已达金牌线。
在我写 M 的时候 Destiny 和张神想出了 A,M 题一过张神就立刻写起了 A。于是 Destiny 找了目前通过数较多的两题 B 和 D。这两题比较简单,B 题我想了十分钟得到了一个单调队列 $O(n+kq)$ 做法,D 我也一眼丁真搞了一个 $O(n\log^2 n)$ 的二分+平衡树做法。然后张神 A 就 wa 了,Destiny 立刻过去打 D 的平衡树,张神和我静态调试 A。我们瞪了半小时没结果,然后 Destiny 也 wa 了。于是我就去写 B。这段时间,我们从金牌线掉到了银牌线。
一直到开赛三个小时后,我终于写完了 B 并过掉,张神也找出了 A 代码的错误,Destiny 也发现 $n=2\times 10^5$ 时二分+平衡树的 $O(n\log^2 n)$ 没法三秒内过并想出了 $O(n\log n)$ 的单二分做法(我口糊的双 log 做法害他调了两个小时)。十几分钟后张神过掉了 A,Destiny 开始码 $O(n \log n)$ 的 D 题。
张神和我开始看 J。我提出了题目的一种抽象,将原题转换为求图的边匹配;张神猜想边匹配存在的充要条件是每个连通块的边数为偶数。我们两个确信这个猜想是对的,在十几分钟的思考后张神提出了 dfs 树构造。这时 Destiny 过掉了 D。他看了看排行榜,告诉我:如果能把 J 过掉我们金牌就有了。我赶紧上机码 J,却在比赛还剩 40 分钟的时候 wa 掉。
两人赶紧过来帮我查错,几分钟后无果,只能让张神赶紧码一份,Destiny 和我到队员机上查错。结束前 15 分钟,张神也 wa 了,Destiny 和我也未查出任何错误。我们都觉得这道题很可能做不出来了。
突然,张神指出我们建图的方式会导致本该不同的点重合为同一个点。张神起初表示这个错误没法改,但仅仅一分钟后他突然又喊道“好像可以改”,冲向电脑改代码,我也随即意识到了修改方法,而且对于我的代码来讲,只需要改一行。张神 wa 了,我赶紧切到我的代码改完,提交,通过了这题。吐槽一下这个系统,评测未通过是绿色,通过反而是红色。
接下来,大家都不再看题,而是对着排行榜分析起来。Destiny 经验丰富,指出某些封榜后交题的队纯属虚张声势;最后他认为我们金牌很有机会,张神却认为不只是很有机会,而是稳了。最后也确实是金。