王展鹏IOI2020参赛总结IOI2020参赛总结2021-04-08 10:41:00阅读量:326

 
 

首先,十分荣幸能够代表中国参加在由新加坡主办的线上第32届国际信息学奥林匹克竞赛,今年由于疫情没法出国,自然也少了很多交流玩耍的活动,顺便吐槽下,开幕式和闭幕式都是全英文的,开幕式除了放选手列表以外几乎都是广告,闭幕式除了获奖名单也都是广告,我英语水平有限,几乎听不懂(不过以往估计也都是全英文的)。不过里面有华为的广告,做的挺好的,不想有的广告一直就是一个人在那管自己说话。不过话说回来,不得不说CCFIOI还是非常上心的,不管是技术方面还是生活方面都做了全面的准备,让我们没有什么后顾之忧。

我们的比赛场地在中科院计算所的一个小房间里,环境布置得舒服整洁。但不知道主办方新加坡怎么想的,明明跟我们一个时区,比赛时间却设置在晚上700-1200,我们只能提前开始调时差,我们提前了很多天就到了北京,因此比赛时状态也还算不错。

目标只是想拿块金牌,压力也不是很大,第一天比赛日,比赛准时开始,我先将所有题目都读了一遍,大致了解了一下每道题的情况。其实我平时的习惯一般都是先看一题做一题的,但由于IOI只有开始的一小时可以提题目的问题,所以只能先粗略的了解完每个题的题意。

准备好机器环境以后,我仍然按照习惯从前往后开题,但思考了40分钟左右plants这题仍然没有什么思路,有点慌张,就转而思考第三题tickets。这题并不难,我很快将此题转换为最大化选择一些卡片减去一些卡片的模型,可能受平时训练的影响,看到输入有k就不由地联系到凸优化算法,因此不假思索得就写了一个凸优化上去,交了好几次一直只能过权值为01subtask,调了好久才发现自己二分范围只设了1e9,实际需要2e9,改了就通过了,这时候时间已经过去了快2小时。但其实心态还算可以,因为觉得凸优化这种算法国际上应该也不是人人都会(但实际上有简单得多的贪心算法)。由于觉得第一题不太可做,就开始思考第二题。第二题其实是一个比较良心的题目,根据subtask的提醒一步一步做下去很容易得出标算,我中间没有考虑到两个点的环情况是不合法的卡了一会,但由于这个程序过了没有不合法情况的subtask,所以根据这个提示也没多久就调出来了。

第二题得到96分以后,感觉自己特别赚,因为p[i][j]=3的看起来特别复杂的情况我不会竟然能拿到96分。之后又想了会plants还是没什么思路,觉得supertrees 只剩了4分肯定不会有多难,画了画图觉得出现 p[i][j]=3就不合法,果然通过了。

这时心态特别好,开始研究第一题,再尝试了很多乱搞都是0分以后,突然想到当k×2>n时,每次可以唯一确定最大值,这样就做完了。突然有了进展让我很振奋,发现其余情况也可以采用类似的思路,确认出一个不严格递减的序列,通过一些技巧支持快速查询就可以了。这时还有快两个半小时,我内心大定,有惊无险地在调试过若干错误以后通过了此题,距离结束还有二十分钟,成功成为中国队中最后一个AK

考完马上得知全球七个满分,中国队四个,这个成绩大概是中国队历史最好的Day1成绩了。我个人认为原因是最体现区分度的plants这题,达到满分需要一些数据结构和优化技巧,而这个恰恰是身经百战的中国队比较擅长的内容之一。比赛结束后,考场外大家谈笑风生,其乐融融的,几乎没人讨论赛题。

回去研究了一下金牌线,金牌占十二分之一,大约是在232分左右,也就是说Day2只要232分就能稳拿金牌了,所以Day2之前心态挺好。比赛开始后,我选择先开看起来比较简单的mashrooms,很快想到一些常数较大的根号算法,实现了一个80的程序。由于第三题题意比较复杂,所以我转而思考第一题biscuits,不太有什么思路,因此我选择先尝试第一个看起来特别简单的subtask,但我的做法也略微有些复杂,并且完全无法推广。不过冷静下来后,把题目的条件转化,很容易发现就是一个简单的DP模型,由于k比较小几乎多项式算法都能通过,很快也就通过了这题。这时才过去了两个小时,而我已经得到了180分,只要第三题再拿一些分数就能确保金牌了,心态好了不少。第三题看起来比较困难,我先从朴素的dfs序(入栈出栈序)开始思考,然后过了一些时间把它从O(n^2)优化成O(n)最后再优化一些常数,没想到挺顺利地花了一个小时就通过了这题。

这时我已经拿到了280分,知道自己已经稳拿金牌了,就优化了一下第二题的常数,卡到244次操作卡不下去了,最后交了很多发,甚至还采取了如果当前是第244次询问就直接随机一个结果等方法,但都没有使分数变高,又没有别的思路,只能以92.62分结束了Day2的比赛。

最后没想到中国队都是92点几分,蒋明润同学以245次操作数比我们三个少了一点点分。我觉得今天比赛三题都不算简单,以为592.62可能可以成为最高分,不过事实证明我想多了,我以为比较难的第三题stations有快一百个AC,第一题也有50个以上AC,第二题也有不少人拿到了比我高的分数。事实上,在Day1 满分的人中,所有人都在292分以上,中国队三个并列第三,一个第七(所以卡常数有多重要)。美国华裔队长William Lin直接AK了,确实是水平上的差距。

这次IOI的题相对容易一些,我取得了第三名的成绩也让我很满意了。唯一一点感悟就是打比赛还是尽力就好,自己的难度估计总是有失偏颇。另外这次比赛很多小国家和地区的选手都发挥不俗,这可能也会成为以后的常态吧,但总得来说,这次中国队还是发挥得很不错的,应该是近几年的最好成绩,我觉得这与现在不断进步的选拔方式与国内越来越成熟的信息学氛围以及领队的辛勤准备是分不开的。也希望中国的信息学成绩能越来越好。

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