周雨扬IOI2020参赛总结IOI2020参赛总结2021-04-08 10:40:01阅读量:359

 
 

首先,我非常荣幸能够成为中国国家队的一员,并且参加在线上举行的第32IOI。在这里我想要特别感谢王宏老师,赵启阳老师,蒋婷婷老师以及其他所有为我们参加IOI作除努力和贡献的老师。他们为我们准备了舒适整洁的比赛环境,为我们辛苦的翻译题目,与新加坡的技术人员进行充分的交流,让我们在赛场上能心无旁骛地做题。我们取得的成绩是与他们的辛苦付出分不开的。

由于疫情的原因,这次比赛采用线上的方式进行。我们的比赛场地位于中国科学院计算所,而选手平时住在不远处的酒店,只需要在考试前30分钟赶到比赛场地即可。

接下来谈谈我的比赛经历。

第一天的题目是三道传统题。第一题plants是第一天全难的一道题目,但是因为第一遍审题时对于tickets没有很好的思路,而supertrees构造比较简单,实现也较为简单,于是决定先去做看上去比较值得花时间思考的第一题。首先我先花了10分钟思考了一下子任务2的性质,但是并没有第一时间提交。然后我尝试分析一个元素是区间内的严格最小值的条件。在分析了30分钟左右后,我想到了正确的判别方法,并且提交了一个 O(n^2) 的算法检验正确性。然后花了大约10分钟把算法复杂度优化至O(n log n)。此时拿到了第一题的44分。

接下来我开始思考如何判断答案为0的情况。首先我考虑的是基于已知的一组合法解找到答案的拓扑关系图,但是这样时间复杂度比较大,因此并没有急着第一时间去写,而是继续思考性质。大约在30分钟后,我分析出来了最终的判断条件,并且尝试使用两个倍增数组加速判断的过程。在20分钟后我第一个通过了第一题。

第二题较为简单,因此稍作思考后进行了简单的构造,花了不到20分钟就通过了此题。然后开始面向第三题。在分析到这题的解题关键就是把元素分成两组,在满足某些条件的情况下,使得两组和的差最大。因此花了大约25min就一次提交直接通过了本题。此时距离比赛结束还有大约2个半小时的时间,于是我开始思考在 tickets 在去除 k 为偶数的条件后是否可以得到解决,但是没有分析出结果。

赛后我得知中国队4名选手全部拿到了满分的成绩。王宏老师在考试结束后提醒说,由于IOI的题目编排是按照题目名字的字典序编排,而非按照难度编排,因此可能会出现第一题最难的情况,希望选手多加注意。而我在开场作最难的题目,并且差点因为花了很长时间没有做出来而影响了心态。因此在第二天我打算换一种解题策略,在花10min左右将所有题目都看一遍后再决定先去做哪一道题目。王宏老师还提醒说,今天有7名选手拿到了满分,同时其他选手得分也较高,因此在第二天的比赛中不能掉以轻心,要以最认真的态度面对第二天的考试。

第二天的题目是一道传统题和两道交互题。第一题 biscuits 在经过若干转化后是一道较为传统的数位DP题,可以直接使用简单的动态规划通过。我再思考了大约10分钟之后就想到了正确的做法,并且大约35min的时候通过了第一题。然后我开始思考第二题。在写出了了使用 400 次询问的简单算法之后,我思考了30min没有任何改进,因此决定先思考没有动过的第三题。

第三题有一个比较简单的同时记录入栈时间和出栈时间的算法,因此我先对其进行了一个简单的实现,拿到了50.32分的成绩。然后我便开始思考如何去除dfs序列中的冗余信息。由于dfs序列上相邻两个子节点其访问顺序一定连续,因此我考虑对于每一个节点只保存其入栈时间或者出栈时间。在经过一段时间的对于求解方法的思考后,我在大约两小时时完成了构造,并且再之后的提交中得到了满分。

接下来的时间大部分都在优化第二题。利用询问的性质,我先将询问次数压缩到282次。在3个半小时的时候,我最后将询问的次数压缩到了244次,从而可以获得92.62分的成绩。但在之后,我所有对这个算法的优化都失败了。在考试结束的时候仍然是这个分数。

对于我而言,这个成绩比较理想,但也有可以改进的地方。在赛后,我得知可以借鉴之前我有做过的另外一道题目的做法。将其套用在第二题确定元素的过程中就可以将询问次数压缩至227228次。如果多反复调用该种策略可以将询问的次数压缩的更加小,也就可以通过本题。但是我没有联想到这个性质并且取得更高的分数,这也是这次参赛的一个小小的遗憾。

值得一提的是,IOI的赛制与国内现行的选拔赛制区别较大,同时在题目编排以及题目风格上也有着较大的区别。我认为国家队员应该加强在IOI赛制上的策略这方面的训练,以更好地适应比赛环境,尽量避免由于策略失误而导致的失分。在今年的赛前训练中,在线的CEOIBOIJOISC的比赛为我们的训练提供了极大的便利条件。

由于疫情原因,这次比赛我们没有机会与国外的选手现场交流。但是我感受到了近几年国外选手在信息学奥林匹克竞赛上越来越高的水平。这也会激励着我们一代代的国家队员不断努力,提升自己的水平。

最后,感谢中国计算机学会为我们提供这次参加IOI的宝贵机会,感谢教练的指导,感谢父母和朋友的关心,感谢所有帮助过我的人,谢谢你们!