邓明扬IOI2021参赛总结IOI2021参赛总结2021-07-13 13:14:36阅读量:22009

 
 

非常荣幸能够代表中国参加2021年第33届国际信息学奥林匹克竞赛(IOI2021)。受新冠疫情影响,IOI2021仍在线上进行。我和队友们在北京市中关村皇冠假日酒店参加了比赛。荷兰选手 Andy Van Horssen因受困于中国境内,也来到酒店与我们一同竞赛,为比赛增添了难得的国际气息。

赛前我的选手身份遭遇了一些质疑。所幸韩领队和叶老师向组委会说明了情况,并未太多影响到我的心态。

IOI day1前一晚是我的毕业典礼。我的母校是北京市人大附中,恰好位于酒店旁边,于是我得以赶去参加。在夜晚的操场上听着毕业歌,我意识到中学生涯即将走向尾声。IOI也将是我OI旅程的终点。若能夺金自然最好,但无论结果如何,我希望自己能享受比赛。

第一天的竞赛较为坎坷。由于知道题目按名称而非难度排序,我先花十分钟阅读了所有题。第一题 candies 像是数据结构,并非我的强项。第二题 keys 乍读之下毫无头绪。第三题 fountains 是我擅长的构造,于是我又读了遍题,猜想连通则有解。此外,70 的部分分看起来很容易。高分而简单的子任务、毫无意义的无解判断,一切迹象都在暗示:这是一道送分题。于是我毅然将前一小时投入到 fountains 的构造中。我先尝试了删去最上最左点归纳的技巧,然而总有一些情况不对。我又试了几种贪心,一时却无法判断正误。

时间过去一小时有余,我却没有丝毫头绪。我的心态有些慌了。听到队友们敲击代码的声音,我决定再读读前两道题。keys 思考了五分钟仍一筹莫展,于是又转攻 candies。扫描线是常见转化,但计算糖果数量我走了许多弯路。我先猜测最后满的时刻是最后一个大于 c 的后缀,思考了十分钟发现不对。经过一段时间的推理,我意识到每个后缀的答案是总和减去最大前缀较 c 的余量。为验证这一结论我提交了一些暴力,虽写错一次,但终于获得了 3 分。知道结论没错,我便尝试优化。我交了一发线段树却仅得到 8 分,对拍后发现优化错了。我又回到最初的式子,发现写成前缀和后有一项单调,只需二分判定即可。终于,我在两小时左右通过了第一题。

过题之后再看 keys,我竟很快有了思路。我意识到只需将tarjan算法修改一下、记录dfs子树的钥匙和边进行启发式合并即可。我花了约20分钟写完,但由于状态不佳,启发式合并忘了insert钥匙。检查半个多小时后终于发现这个问题并通过了此题。

此时还剩一个多小时,我又转向了开场第一道阅读的 fountains。我发现开始的贪心构造似乎可以归纳证明正确,提交之后却只获得了15分。经过对拍,我发现归纳过程需要以 2 为周期;这意味着贪心方法也需在两种间交替。我稍加调试通过了此题。此时考试还剩约 50 分钟。看到身边的代老师还在提交,我默默地在注释中为他祈祷。我又想到了在 OI 中帮助过我的人们,将他们的名字一个个写到注释里表达感谢。没过多久,比赛就结束了。

出场后发现中国队只有我一人AK。鱼大(虞皓翔)和钱哥(钱易)前期都遭遇了不顺,最后时间不太够用。代老师快如闪电地通过了前两题,但fountains一题写了乱搞未能通过。查看榜单发现金牌线约为200分,中国选手均在前列。

两天之间我们参加了code combat,一个写AI对战的比赛。由于网络问题,鱼大和钱哥用我的电脑查看了题目。我尝试了一些做法,却总调不出来,最终获得了倒数第三。结果虽不理想,却算为正赛攒人品了。

day2前我VP了一下 IOI2019day2,比较轻松地通过了后两道题,第一题也获得了99分。感觉竞技状态和代码水平比day1前有所提升。

day2我仍然先读了一遍题。dna一题较为简单,意识到结论后我于 14 分钟通过了此题。想了dungeons十余分钟仍无头绪,我决定先做registers。我比较快地意识到了可以通过 a + (-b) 判断两数的大小,而后加上111111得到mask,再将奇偶位置分开即可并行得到两两的min。代码实现看似复杂,但print语句调试非常好用。一个半小时左右我得到了第一部分的分数。我冷静了一下,发现只需稍加修改就能解决第二部分,于是在两小时左右通过了此题,还剩三小时专攻dungeons。我先写了11分暴力用于对拍,而后在思考部分分时,我意识到原题可以将边权按等比数列分类。于是我以 10 为底交了一发获得了89分,将常数除2之后通过了此题。

比赛还余下两个多小时,我再次在注释中感谢了帮助过我的同学们。

最终中国队包揽了前四,我以较大优势获得个人第一名,可以说是意外之喜。赛后我们四个选手一起吃烧烤庆祝这次的好成绩。

我这次IOI的好成绩得益于良好的心态和稳健的考试策略。IOI需要冷静,即使前期不顺利也不应慌张,而要稳扎稳打地做完后续题目。当水平足够高时,一道题的失利并不足以让你掉出金牌线,但若因此心态爆炸则可能直接崩盘。建议未来的选手能平常心参赛,以享受考试为目标,而不要执着于拿前几名或夺冠。这样即使做题不顺,仍有享受比赛、达成目标的机会,而不至于情绪崩溃。至于策略,我制定的方案是在每道题上至少认真思考半小时、至少认真工作一小时:就算某道题目不顺,其他题的时间也要花满。这样,即使有一题发挥失常,其他题仍能得到应有的分数;而夺金往往有一题的容错。未来的国家队训练或可多引入一些易猜错结论题/中等题很多的场次,帮助选手打磨策略以及做好应考的心理准备。

感谢父母和朋友同学们一直以来对我的信任和鼓励,也感谢老师们在赛前为我作的心理辅导工作。领队韩老师、教练叶老师、谷老师,我的三位队友在这次比赛中也给了我很大的帮助。我的发挥和他们是分不开的。

祝我的大学生活顺利,祝以后的选手们加油。

完结撒花owo