刚刚结束的ICPC2023沈阳是自然选择号的最后一场 XCPC 区域赛,很高兴也很幸运能拿到校排名 rk4,圆了一个这半年才开始做的梦。在这里讲一下这支队伍的故事。
组队、训练
本来和@wjy666(aka maple)打完 EC Final 之后是想要退役的,因为一直处在基本不怎么训练只打比赛的状态,如果打不出更好的成绩也没什么意思了。之后在教练的建议下吸纳了大一零基础的大腿@geruome,想看看有没有可能冲击一下 WF。CCPC Final 是我们这支新自然选择号的首秀,当时没训裸打打了银。虽然成绩不亮眼,但是我们发现三个人的状态是舒服的,打好配合说不定真的有机会。
那就试试吧。
虽然这时候信心几乎为零。
后面一段时间在忙保研,于是8月初的 thu camp 成为了我们开始训练的第一站。打得很惨,场场被按在后排。坐在我们后面的银色子弹,几乎每场比赛都从头到尾压着我们打,给我打得有点自闭,不知道这个状态怎么能赢。现在看来,当时打得不好完全是因为三个人都好久没写代码,并且还没开始磨合。三个人的磨合,可能比个人的硬实力更为关键。
开始狂训是在9月。平均2天一场 vp,赛后再去补知识点。geruome 训练热情非常高,带着我们一起泡在俱乐部补题。这一个多月的时间打了差不多 20 场比赛,写题写多了手逐渐热了起来,我开始有了一点信心。期间去打了一场湖南省赛,也是拿到了第一次 ak。
秦皇岛、西安、桂林
秦皇岛赛前,信心差不多四成。
因为打了几场成绩还不错的 ucup,也很想在现场赛施展一下拳脚。不料,最终连金牌都没有拿到。maple 过了超高难度的 K,我最后 I 题写了一个多小时还是没有调出来。
西安的最后20min,是我们这辈子第一次看到出线的希望。当时我和 geruome 10min 内连续通过 I 和 A,过题数达到了8。此时压力全部来到了 maple 身上,这场能不能打到前五可能就看他能不能把 B 调出来。用他复盘的话来说,在我们8题的时候,他一瞬间被“过了就能出线”的压力给压垮了,完全不能静下心来调试。最终因为有一个变量名没改过来,还是没能通过。
但是这场比赛,让我们看到了希望,我们好像就要触碰到梦想的边缘了。即使在强队如云的情况下,只要我们发挥出正常水平也是可以一战的。面对后面强度预计不如西安的沈阳,我觉得我们有八成胜算。
然而之后的桂林,也是简单题卡住,H 没有人想到可以从父亲节点删元素。maple 深陷极具迷惑性的 L,本应该会做的 E 却因为没有早看而没能写完。
打了三场 XCPC,每场都暴露出来各种致命的问题,其实这些问题的根源还是比赛策略的问题。从秦皇岛放着 M 不做,C 不看,到西安没有把题目给到适合的人,再到桂林做不出 H 做了半场 L,还没有早看到会做的 E,关键的决策好像没有一步是对的。虽然复盘的时候,我们认为每一场的失误都是在赛中可以预判并即使修正的,但到了沈阳真的就能避免这样的问题吗?我不知道。
这时候我的信心又降回40%了。
这三站打完没什么心情合照了,放一张省赛的图
线下练手的机会已经没有了,下次就是沈阳的最后一舞,我需要静下心来沉淀一下。想要打出好的成绩,就必须把我们的特长发挥出来。我们三个的风格太不同了:maple 算数飞快,擅长贪心、dp 、构造等一切不需要科技的题,然而却不会写线段树;geruome 数据结构水平高超,擅长写恶心题以及计算几何,但好像不是非常懂 tricks,有的题会无从下手;我技能树比较全,对题目方向猜的比较准,思维比较灵活,但是上机脑子容易发懵,细节稍微一多就写不对。我们三个人单打能力应该都不大行,但合在一起恰好优势互补,哪种类型的题都有人做。
然而本应该分工明确的我们,在复盘的时候,总是有某段时间三个人都想不起来自己做了什么,好像没有任何进展,5h的比赛被我们打得像4h。其实,一道题目其实就那么几个关键点,思考方向正确的话不会花费太长时间的;如果思考方向错了,那就是在无用功,扔给队友或者一起讨论都要比一个人死磕要强。于是我们决定要调整比赛的节奏:每个人先看足够多的题,分给合适的人。如果一个人卡题了,那就大家一起看这个题并把它做出来,尽可能减少无意义的罚坐。
在最后两周的训练中,我们主要往年的区域赛题目为主,目标不再是做出难题,而是主要训练在可做题较多的情况下如何写的又快又稳,以及卡题时要怎么做。我让自己多读题,每道题扔出一些我的思考,然后分给对的人去做,我尽量不去陷入细节较多的题目。如果一道题我和队友讨论出来了,那就尽量扔给队友写,我再去开别的题。
出发前,我的信心处在叠加态中。想到我们没有人写过难一点的计算几何,我的数论水平还不够高超,Todo 里还有很多东西没有梳理……但没关系,我选择相信我们(洗脑)。
沈阳
两周没有参加比赛,热身赛坐在不大且摇摇晃晃的桌子前,居然有一点陌生的感觉。虽然两个略难的题目都没能通过,但没怎么影响到我。因为我知道,我们的训练量已经有了,默契程度已经够了,这两个月的训练成果,就看明天5h内的发挥了。挺残酷的,但这就是 ICPC,不是吗?
正赛总算开始了。拆开信封 2.5s 之后,geruome 就通过题目名发现签到题。之后 maple 也迅速过 E,此时排在 rk1。我读了 I,感觉是没什么技术含量的讨论题,应该是要过的(伏笔1),果断扔给 geruome。简单讨论后我发现 J 是简单题,贡献一发罚时后通过了(伏笔2)。这时候稳健跟榜,maple 看了 K 说一眼数据结构,直接丢给我,我看了看就写了,maple又迅速通过了 M。B 很快想到了一个 n^3 的思路,但是细节较多。于是先看了 H,猜了个做法扔给了 maple 去细想。在我上机写 B 的时候其实还没有完全想清楚,心里是没有一点底的,但我知道这道题必须过,所以只能先硬着头皮写,等着队友把我换下来想细节。当我发现我怎么也想不清楚细节的时候真的有点慌了——我写题的时候,信心会给我正反馈,当某道题我没有信心写出来的时候,我就写不出来,当我有信心能写出来的时候,我就能写出来。这时距离比赛结束还有1:40左右,手里还有三个没过的题目。我心里发毛,训练赛遇到这种情况,我基本就知道这题是出不来了。但是,今天是我最后的机会了。于是我出去上了个厕所,告诉自己说:没事,我今天就算没有别的任务,剩下的时间只要把这个 B 做出来就算没有遗憾了。强迫自己冷静下来以后,发现根据对称性能把很多细节都给扔掉。于是我思考清楚后,等着上机重构了一下代码,在 4:29 通过了。这期间,geruome 把 D 给过了,I 写了大部分。这时候,情况变得和西安一样,压力全部集中在了 geruome 身上。我们都知道,只要过了 I 就肯定能出线。看着 geruome 独自调试,我却帮不上忙,心里比我自己上机还要紧张。终于在比赛结束前40s,发现了可能是最后一个错误,但已经没有时间改完了。
比赛结束,全场掌声响起,我觉得没了。掏出手机想算一算到底有没有机会,但紧张到根本没法静下心来算罚时。看到出去打探的 maple 竖着四根手指回来的时候,我挤压了许久的情绪才终于释放了出来。
稍有遗憾的是,我们差 11min 罚时就能拿到杯子。如果我签到 J 没有 wa,我们三个就能一起上台共同举起季军奖杯。不过没有关系,rk4 也已经足够美好了。
后记
算了算时间,距离我敲下第一行 “Hello, world!”差不多刚好六年半,我也终于可以给磕磕绊绊的算法竞赛生涯画上一个圆满的句号。
如果说我们在这两个月学到了什么,一是经验,尤其是现场赛的经验。三场比赛,从 rk28 到 rk8 到 rk8,每一场比赛我们都能从中发现很多问题。比如秦皇岛 I 题,告诉我我不适合写细节多的题;秦皇岛 M,桂林 H,告诉我们卡住的题要大家一起看;西安 B,告诉我们题目要今早交给擅长的人。二是默契,三个人泡在一起训练的过程知根知底。谁擅长什么不擅长什么都互相了解的很透彻,于是在比赛中话说一半就能够心领神会,沟通非常高效,才能发挥我们各自的长处,真的达到了 1+1+1>3 的效果。
感谢两位给力的队友,和我一起实现了这个去年还不敢做的梦。还要感谢明日之风和金色传说出线 23WF 给我们的激励,以及感谢教练的 push。
祝 ALPC 越来越好。
说一下我 B 的做法吧,题解好像是 O ( n 4 ) O(n^4) O(n4) 的,我的做法可以做到 O ( n 2 ) O(n^2) O(n2),不知道大家是怎么做的。
定义 f ( n ) f(n) f(n) 表示长度为 n n n 的 turning permutation 中,1 在 2 左边的排列有多少。枚举第一个数填 i i i ,那么 1 , . . . , i − 1 1,...,i-1 1,...,i−1 和 i + 1 , . . . , n i+1,...,n i+1,...,n 之间是独立的。于是有 f ( n ) = ∑ i = 1 n f ( i − 1 ) f ( n − i ) ( n − 1 i − 1 ) f(n)=\sum_{i=1}^nf(i-1)f(n-i){n-1\choose i-1} f(n)=∑i=1nf(i−1)f(n−i)(i−1n−1) 。因为要求字典序最小,所以从小到大枚举每个位置填什么,需要计算确定一个前缀的 turning permutation 有多少。同样,已经填了的数把没填的数分成若干个连续的段,每一段之间互不影响,任意一段要求长度为奇数,并且段中第一个数在第二个数的右边,因此方案数可以通过 f f f 数组和组合数计算出来。确定前缀后,计算一次方案数是 O ( n ) O(n) O(n) 的,但是按字典序枚举某个位置时只会将某个连续段划分为两段,因此也可以根据之前的答案 O ( 1 ) O(1) O(1) 计算,这样总复杂度可以做到 O ( n 2 ) O(n^2) O(n2)。