杨骏昭IOI2019参赛总结IOI2019参赛总结2019-08-20 09:31:34阅读量:2498

 
 

首先,十分荣幸能够代表中国参加在阿塞拜疆举办的第31届国际信息学奥林匹克竞赛。这次比赛在阿塞拜疆首都巴库举行。巴库是一个环境优美的城市,不仅有很多具有创意的现代化建筑,还有很多具有异域风情的欧式建筑。我们住在运动员村,宿舍十分宽敞整洁,楼下还有供选手放松休息用的娱乐室。阿塞拜疆的志愿者和guide们都很热情,选手们之间氛围也很好。这次ioi每次比赛日后都有一个参观日,还设置了很多丰富多彩的活动。总的来说这次ioi体验非常好,超出了我的预期。

我们的比赛场地在国家体育场,所有三百多个选手都聚集在这个场地中,从入场口看场地感觉十分壮观。正式比赛当地时间九点开始,下午一点结束。比赛开始前一天晚上guide会收取选手所有的电子设备,于是我们晚上只能去娱乐室放松身心,很早就休息了。

第一天比赛日,比赛准时开始,我先将所有题目都读了一遍,大致了解了一下每道题的情况,准备好机器环境以后,决定先做shoes这道题。想了一会我发现将同种颜色的鞋匹配后就可以转化为所有鞋颜色两两不同的情况,之后对每两双鞋计算让它们相对位置正确的最少次数,就可以得出答案的下界。我猜想这个下界可以达到,于是就想写一个平方算法试一下。感觉刚开始有点紧张,再加上写程序的时候特别急,这个算法我当时就写挂了,提交上去后只有10分。(后来发现这个东西其实非常好证)

当时我粗略查了一下程序,感觉没什么问题,于是开始怀疑算法正确性。但是想了一会觉得这个算法看起来非常正确。当时感觉不能再这样浪费时间了,准备写一个暴力开始对拍。但是写完暴力后发现暴力也WA了,开始怀疑人生,甚至怀疑数据的正确性。不过很快发现暴力写挂了,对拍后发现那个算法也写挂了,改了改交上去就没有WA了,优化了一下就通过了这题。这时距离比赛开始快一个小时了,感觉自己太急躁了,浪费了很多时间,不过这题通过之后心静下来了一些。

接下来去做rect这题,很快想到一个O(n^2 \log n)的做法,但是当时觉得这么大的数据规模不一定能过,而且自己的做法太烦了,肯定有更简单的做法,就没有立刻实现。我又想了一会,没有什么突破,决定先去做split,准备预留一些时间待会再写这个算法。

split很快想到一个部分分的做法,于是开始想正解。我猜想正解一定是一个比较优美的算法,但是我完全没有头绪,并且在双连通分量、ear decomposition方面想了很久,但是完全没有突破,决定放弃这题的正解。虽然投入了很多时间,但是放弃的主要原因是当时我还完全不知道怎么用题目三分之一的一个非常特殊的条件,而且我想的算法实现十分复杂,剩下来的时间根本不够写完这个算法和rect的算法。于是我很快写完部分分后就回去做rect

rect我准备先写一个O(n^3)的暴力算法,再将其中两个部分用数据结构优化达到O(n^2\log n)。当时我的实现不是很优美,但是还是写完并且调过了。优化达到O(n^2\log n)后我发现我的算法可以过前七个包,但是理论上第七个包和第八个包对我的程序来说没有区别,应该可以获得满分才对。我发现我第八个包有一个点显示的是RE,这个系统的RE也可能由MLE导致。但是我看了一眼提交记录中显示的内存,只有内存限制的五分之一不到,就开始找数组越界之类的问题。(比赛结束后才发现这个内存其实是编译内存)我被这个问题困扰了快四十分钟,最后终于在很多次尝试后通过了这题。(其实我还发现我的算法可以进一步优化到O(n^2),但是由于不是TLE,并且实现起来太麻烦了就没管了)

此时离比赛结束还有50分钟不到,就继续去想split正解,但是仍然没有突破。最后写了一个随机乱搞,但是也没有获得分数。

第一天分数240分。感觉第一天考试发挥得很不好,但是从结果上看还行,因为我没拿到的分数应该是非常难拿的。我预计我的名次应该挺靠前的,但是没想到自己名次并列第8名,竟然有25名选手大于等于240分,顿时感觉自己金牌不一定保得住,毕竟我达到这个分数用时还是挺长的。感觉外国选手比自己想象中的厉害多了。(虽然之后冷静了一下发现240分不是很难拿)

第二天比赛日,比赛延时了差不多30分钟才开始。不过在延时的这段时间中让自己的内心平静下来了,刚进场的时候真的有点害怕自己会拿不到金牌。比赛开始后,看到一道构造题、一道提交答案题和一道传统题。看了一眼提交答案题的评分方式,知道这次金牌区选手肯定没有同分的了。开场我准备先做传统题。

walk这题看上去像一个数据结构题,但是想了一会发现不太对劲,我猜想这题肯定存在一个不需要复杂数据结构的算法,但是我并没有什么思路。我准备先做57分部分分,虽然有了大概的思路但是仍然想不清楚,感觉自己智商不太够用。写完10分暴力后又想了一会部分分做法,但是感觉一时半会做不出来,觉得不能再浪费时间了。此时距离比赛开始已经一个多小时了。

然后我开始做vision这题。我先想了一个O(n^2)暴力,然后又想了想感觉优化一下就能O(n\log n)。实现了一下就过了这题。此时距离比赛开始两个小时。

接下来我去做line。这是一道提交答案题。我思考了一会,写一个O(n^2)贪心选取下一个点的算法,得到了70多分,调了调参数后改进到了84.8分。我觉得再改进下去意义不大,不如去做walk

walk我又想了很久的部分分算法,想到一个基于我推出来的结论的一个维护单调栈的做法。但是由于时间不多了,我内心有点急躁,写了几个假算法。中途我还抽空写了一个对拍,用来验证算法正确性。后来我冷静了一下,又推了几个结论,获得了一个非常简单的只用set的算法,通过了前四个子任务。我还发现我的算法中没有用到和柱子高度有关的信息,所以子任务三和子任务四是没有本纸区别的。

最后还剩下半个小时(比赛延时了15分钟),我想了一会walk正解。但是发现我这个做法拓展到正解需要很多繁琐的细节。最后十五分钟开始改进提答,非常遗憾的是最后改进的1.18分没有来得及提交上去~~,不然可以让中国队团体总分排名前进一名~~。其实我最后的最优策略应该改进提答而不是想walk正解的,这样分数还能再多一些。

这次比赛最后时间我比较慌张(特别是最后十五分钟),再加上我以为walk应该过了很多人,出场后有一瞬间我以为自己拿不到金牌了。不过从结果上来看我的成绩还是不错的,两天最终排名第五名。

回顾这两天比赛,我觉得我有很多做得不够好的地方。但是从分数上来看,并没有太大的失误,我还是比较满意的。

最后是给以后参加ioi的选手一些小小的建议。

- 一定不要轻视对手的实力,金牌并没有那么容易。但是也不要过于紧张,只要发挥出自己的实力就行了。

- ioi题目的数据规模一般来说都比较大,有的时候不要觉得自己的算法肯定会TLE,可以在不浪费时间的前提下尝试。

- 考场上心态还是很重要的,一定要冷静思考。

- 由于ioi赛制和oi赛制的不同,有些考场上的策略也应不同。

- 一定要看清楚CMS系统给的时间和内存!那个是编译时间和编译内存!


最后衷心感谢所有帮助过我的同学和老师们,没有你们就没有今天的我。感谢我的父母,是他们一直在背后默默地支持着我。感谢这次带队老师为我们那么辛苦地翻译题面。终于退役了,要跟我所喜爱的oi说再见了。希望oi以后可以越来越好。