代晨昕IOI2021参赛总结IOI2021参赛总结2021-07-13 13:14:36阅读量:1

 
 

首先,我非常荣幸能够代表中国参加由新加坡主办的第三十三届国际信息学奥林匹克竞赛(IOI2021)。受新冠疫情影响,今年的IOI仍然采用了线上比赛的形式,于619-28日在世界各地同步举行,共有来自88个国家(地区)的355名选手参赛。

今年国家队选拔更改了赛程,在2月份时就确定了国家队的名单,这让国家队员有了充足的时间备赛。在5月底,国家队还集中到宁波市镇海中学进行了赛前的统一集训,针对IOI的题目风格做了一些针对训练。为了照顾到世界各地的参赛选手,这次比赛的时间定在了晚上6点至11点。在备赛过程中,我们同时在教练组要求下调整时差,在凌晨1点左右睡觉。

本次比赛中国队在北京集中参赛,选手居住在中关村皇冠假日酒店,同时比赛场地就设在了酒店的会议室,环境非常整洁舒适。赛场按照主办方的要求在四周设置了摄像头,并且在大屏幕上将北京时间投影了出来。选手也需要提供比赛时的录屏,以确保比赛的真实性。今年有一位荷兰队的Andy同学由于种种原因和我们在同一个场地参赛,他的中文很好,我们也和他进行了一番友好的交流。值得一提的是,第一次试机时我们发现提供的键盘不太好用,结果第二天就进行了更换,参赛体验非常好。

第一天比赛日。由于有去年的教训,领队老师也在赛前和我们多次强调:IOI的题目是按照字典序排序的,与难度无关,我在比赛开始时先阅读了一遍所有题目。这时我对前两题,尤其是第一题有了一定的思路。

对于第一题candies,首先肯定要把操作对每一个糖果盒离线下来。由于之前训练过类似的套路,我很快注意到:对于一系列操作,如果前缀和的极差大于糖果盒的容量,那么不管初始有多少糖果,进行完这些操作后的糖果数量都是确定的;同时,如果极差小于容量,可以对一个初始值O(1)计算出进行完这些操作后的结果。所以,可以写一个线段树维护前缀和的极差,并通过类似二分的方式快速求出答案,时间复杂度为O((n+q) log q)。我在比赛开始约30分钟时实现了这个做法,并通过了第一题。

第二题keys,题目只需要求出可达点数最少的点集,肯定要从这个方面入手。我隐约感觉到:如果a号点能走到b号点,那么b号点肯定不劣于”a号点。所以,最开始可以尝试为每个点随便指定一条可行的出边,这时形成的树就可以被删去,形成的环套树就可以缩成一个点,再接着跑下一轮。这个做法十分类似于Boruvka,时间复杂度为O((n+m) log n)。我花了10分钟冷静思考了一下它的正确性和细节之后便开始实现这个做法,并在比赛开始约一个半小时后通过了本题。

剩下的时间我都在思考第三题parks。因为本题提供的示例程序对特殊情况的判断有一定误导,所以我浪费了一些时间,花了一个多小时拿满了70分的暴力分。可惜的是,我一直在思考优化寻找生成树的方法,但没有发现能够通过此题的思考方向。最终我也没有通过这个题。

赛后我得知队友邓明扬获得了全场唯一一个满分,中国队的整体排名也非常靠前。同时我也得知我通过前两题的耗时在所有选手中几乎是最短的,只是非常遗憾我没能通过第三题。

第二个比赛日,我知道第一试的领先较大,只需稳扎稳打即可确保获得金牌。比赛开始后,我先把所有题目看了一遍,发现第三题是一个造计算机题,而且第一题非常简单。

我首先很快通过了第一题,接下来开始看第二题dungeons。思考了一会我发现,打倒一个能力值接近的敌人的收益是非常大的,对这种性质的问题有一种处理方式:分段考虑英雄的能力值,当能力值处在(2^i,2^(i+1)]时,求出走多少步以后能力值会超出这个区间。发现这只需要打倒最多一个能力值在这个区间的敌人,而其余敌人的贡献是确定的,所以这可以用倍增来解决。这个做法的总时间复杂度为O((n+q) log^2 n),我在一个多小时的时候提交了这个做法,获得了63分。

这时我决定先看一看第三题registers,然后再回来补第二题后面的分数。我发现第三题比较两个数x,y的大小时,逐位比较肯定通过不了,就开始思考别的比较方式。但是,我并没有发现可以直接利用题目提供的加法操作提取x-y的符号位,实现了一个利用倍增在O(log k)的时间里比较两个数的做法,完全没有用到最关键的加法。我对这个做法进行了一些常数优化,通过了1235四个子任务。

在对第三题的代码进行优化常数的过程中,我回头看了一下第二题,发现第二题的子任务2很容易实现,所以我花了一点时间通过了第二题的子任务2,多获得了26分。剩下来的时间,我一直在尝试思考第三题,但是到最后也没有什么进展。第二试我的最终得分为235分。

出考场后我发现队友们第二天的得分都比我高,而且等到最终的榜单出来后,我才得知:中国队本次IOI包揽了金牌前四名,而且第一名邓明扬获得了600分满分!中国队以绝对优势获得了团体第一,也创造了IOI首次由一个国家的选手包揽前四名的历史。这次中国队取得了如此优秀的成绩,不仅是因为题目风格中国选手比较擅长(还有队友实力强劲),这与我们做的充足的赛前准备、国内竞赛日益成熟的训练体系也是分不开的。

最后,感谢CCF为我们提供参赛机会并精心组织了这次竞赛,从赛前集训开始为我们提供了诸多支持与帮助;感谢林盛华教练对我的关心与指导;感谢父母;感谢所有帮助过我的人。最后的最后,祝中国的信息学竞赛越来越好。