杨懋龙IOI2018参赛总结2019-06-11 17:25:22阅读量:3772

 
 

首先,我很荣幸能够成为中国队的一员参加在日本举办的第30届国际信息学奥林匹克竞赛,感谢领队老师们为我们翻译题目,感谢谢秋锋老师对我多年来的指导。同时感谢主办方对比赛的重视与支持。

这次比赛在日本进行,时差只有1小时的差距,气候和中国差不太多,这对我们来说是一个好消息。但是伙食的话,虽然是以大米为主食,但其他食品过于清淡,还是有点不太习惯。

这次我们的guide是一个中国留学生,人特别好,交流起来没有问题,也感谢他为我们提供的向导和翻译工作。

回到比赛本身,试机赛的题目与之前网络试机赛的题目相同,一个提答,一个交互,两个传统。

Day1的比赛,我们很早就进入了赛场,但因为一些原因比赛推迟了很久才开始。我也因此受到了些影响,在正式开始前都十分的紧张。拆开试题袋后,我先仔细地把所有题目看了一遍,但此时对于题目都还只有比较基础的思路。因为当前思路的得分较少或代码实现很简单,我便没有立即开始写代码,而是选择先进行进一步思考。虽然这种决策没有对我自己产生什么影响,但似乎令场外的教练十分紧张。

Combo这题是我唯一解决的一个题,看数据范围可以很显然的发现,这题显然是要求逐位确定,于是便先提交了个2N的做法。但在之后的优化上,我一开始走偏了,往多次询问确定多个位置上走了,在思考了一会无果后,我切换到其他题思考了一会。再回到这个题的时候,我重新看了一遍题目,意识到可以是将一个位置上的三种情况分别对应三种不同的返回值。这样便解决了这个题。

对于剩下两个题,我看完题,较简单的思考了一下后,感觉seats的前四个subtaskwerewolf的前两个subtask都很简单,并且werewolf的第三个subtask仔细思考一下应该也不难。在完成了combo那题后,我实现了这几个subtask,但在之后的很长的一段时间内,我都一直没有进展。

在比赛的最后一个小时,我发现seatssubtask5可以转化为统计段数,这可以用线段树解决。我在实现完这个后,打算把它推广到subtask6上,但是我没有找到能限制它为一个正方形的条件。当时时间也不多了,我认为不太够便没有继续思考。考完讨论后,发现这个实现并不难。在werewolf这题上,我虽然思考了很多,甚至都想到了所需要的数据结构的功能,但就是没有想到并查集树。这反映出了我对于这一知识点的不熟练。

最后的结果是第8名,不好也不差的名次,比较了与前面的差距,主要是差在werewolf上,中国队的其他人都做出来了。但因为我做出来了seatssubtask5,所以差距没有那么大。

Day2的比赛相对于day1来说,我做得比较顺利一些。

Doll这题,很显然地会往满二叉树上想,但由于我一开始弄的是保留左边的节点而删去右边的,这样需要一些新节点来保证每个点访问偶数次,所以分数一直不高。在之后重新思考的时候,发现只要修改成保留右边的就可以正好解决问题了。

Highway这题,显然是要找一个序来二分,一开始思考前两个subtask,发现dfs序和bfs序都可以解决。再进一步思考,发现在这个题上bfs序的性质比dfs序更好。明确使用bfs序后,再稍加思考,便得到了90分算法。本打算进一步优化,但是怎么也无法优化2次。

Meeting这题,前4subtask都比较好拿,也就subtask4写起来稍微复杂一点。在比赛的最后时间,我都在尝试做最后一个subtask,但始终也没有想出来。并且这个subtask全场没人做出来。

最终,我两天的总分是469,和第一名有30分的差距,感觉还是有点遗憾,因为还是有自己没能发挥应有水平的题。

总结这次IOI,和往年的题目相比,对于数据结构的考察增多了,这对于我们是优势。但放到题目上,数据结构并没有成为题目的关键点,考察的重点依旧是选手的思维能力。我认为对于思维能力的训练依然要是今后参加IOI的选手的训练重点。

因为比赛有实时反馈,这对于选手的策略也会有所改变。实时反馈机制可以让选手避免许多不该犯的小错误(看错题、调试语句没删等)。但这种实时反馈机制,也具有一定的弊端。因为只有极小数据范围的样例,所以当提交的代码错误时,可能会无法及时区分到底是实现错误还是思路错误,因此浪费大量时间,影响选手心态。并且,今年还在之前的基础上,增加了能够看到三个题所有人分数总和的比值,就我个人而言,我认为这个功能的意义不大。目前感觉唯一的意义就是在1~2小时的时候,如果一个题的比值远远高出其他题,那么这个题极可能是个很容易拿高分的题目。但是我认为能够代表中国队参加IOI的选手也都能够直接从题目中看出来。


总之,这次IOI虽略有遗憾,但我认为我发挥得还是不错的。主办方和guide都特别好,我们也和其他国家的选手进行了交流。我想这次IOI会是我人生中一段难忘的经历。