ICPC校赛小记&感想

yuanheci 2023年11月27日 275次浏览

—— 一腔热情最终还是在失败中落寞离场

  就以这样的形式记录一下吧。

  今年的ICPC校赛原以为是最有希望的一年,队伍实力相较去年也有了较大提升。

  初赛中题目过得很顺(除了我上来签到题一发WA),队友猛猛发力,队友BRR更是在一道2D Gray Code题中做出巨大贡献,立马就想出了关键思路,帮助我们队一度领先到11名。最后在一道树上问题上浪费了很多时间,和CQQ讨论后,我立马就有了思路(然而理解错了题意),喜提一发WA,和CQQ讨论重新确定题意后,CQQ提出了一系列想法,包括确定根来构造树、树平衡等操作,久久没有结果。最后还是BRR加入战斗,提出了向对方那边靠近的核心思想。我顿时醒悟过来因为是一棵树,所以两个节点之间的路径是唯一的。因此找出路径后,各自再染色各自的部分即可。于是快速找出路径,染色,最终在结束前3、4分钟AC了这道题,以AC6/7的成绩RANK 18,初赛结束后我们都很高兴,笑称今年是"最后希望的一年"。

  决赛前一晚上果不其然又失眠了,大概3点才睡着。我和BRR大概8点半就到了赛场,CQQ不久后也到了,9点开始热身赛前我们还被邀请到台上拍了合照。热身赛开始后,第一题输出a+b,第二题是一道交互题,我们都对这种模式不太熟,于是就不再做了。没想到之后的正赛中也有交互题。。。

  很快就到了10点,正赛开始,CQQ立马打开文件袋分了赛题,我和BRR负责先找签到题,CQQ从后往前看题。很快我们找到了签到题,在2分钟的时候一发AC了。然后我就看到了A题,是一个构造对称图形的题目,想了想感觉想不到奇数的特殊情况,于是扔给BRR。同时我从BRR手里接过D题,开始了这次比赛最让人绝望的调试。

  D题限制内存空间为4M,我一开始并没看到,题目思路并不难,于是我写了个二分后提交,得到了一个RUN ERROR,但是我一度不清楚这是什么意思,甚至以为是哪里数组下标越界了中途BRR和CQQ一起在看A题,也没构造出奇数的情况,后面CQQ看出了E题博弈,和BRR讨论后发现没什么问题,一发通过了E。队友后面又去开了F题(交互题,问4次操作猜出数字)。中午草草吃了汉堡,我还在调D题,一直沉迷于二分(开两个数组会内存超限,于是开一个2.8M),但是又会有一些小问题,于是又贡献了几发WA。于是我又换了multiset去做,用二分和删除来做,接过又是TLE又是内存超限,搞得我心态有点小崩。时间一分一秒地流逝,队友也还没看出A题和F题的正解,这个时候全队陷入了困境。我这边卡题了,队友那里也还没出思路。看着榜单上其他队一个个地过题无疑给了我们很大的压力。之后BRR说A题要不奇数情况一个个试过去,从5开始,大不了多WA几发,正打算这么做,突然发现其实大于5的奇数都可以分成5和一个偶数,因此如果5可以,那么大于5的奇数也一定可以,就这样一发通过了A题。此时我还没调出D题,中间我让BRR去看D,我去开了G题图论,G的题目不难理解,我写完代码过了样例,然而提交后确WA了,中途改了几个认为不对的地方,还是WA,真的WA麻了,场面就这样僵持住了。直到比赛结束前10分钟,我看出了D题当前写法的一个解决方法,就是它的值域范围是很小的,根据这一点就可以大做文章!于是我快速写完代码提交,得到一发内存超限,最后极限魔改,把vector改成了手写数组,终于通过了D题。

  后话:D题其实很简单,赛后看题解甚至用不着二分,这么小的值域范围开桶排序啥的搞一搞就行。如果我状态好一点能快速切掉D题,和队友一起去看别的题,最后的结果会不会不一样。

  这次比赛前面的题都很trick,完全没用到什么复杂的数据结构和算法,就是看出性质就能直接写出来。这种赛题的话我觉得还是有点看状态和运气,队友其实思路想得也不慢,由于我卡D题了,士气逐渐低迷,后面导致我和BRR“突发恶疾”,笑嘻了,这样就比较难了π_π。

  赛后我们没有去滚榜现场,也没人拿气球,又打铁了。就这样,在比赛结束的一片热闹场中悄悄地离开了。我知道大家都很难过,这样的结果大大跌出预期,甚至不如去年的排名,实在让人难以接受。

  明年就找工作了,之后大概是不会参加算法竞赛了吧,以这样的结局离开,多少有些不甘,但扑面而来的寒风似乎也想告诉我,这此生仅有的机会也已离我而去了。

  从长远来看,此时离开算竞也许是最好的抉择了,可以有更多时间花在嵌入式上了,Kernel、RISC-V,NET,还有好多东西可以去学习和探索。也可以有更多时间花在科研上,毕竟快要开题了,还没好好准备呢。

  最后感谢我的队友BRR、CQQ,和我一起并肩战斗了两届竞赛~~