钟子谦IOI2019参赛总结IOI2019参赛总结2019-08-20 09:30:48阅读量:22765

 
 

很荣幸成为中国队的一员参加在阿塞拜疆举办的第31届国际信息学奥林匹克竞赛,感谢CCF和科协组织竞赛,感谢领队老师们帮助鼓励我们和为我们翻译题目,感谢黄志刚老师、魏丽真老师、宋立林老师、黄晓燕老师对我的关心和指导,感谢主办方对比赛的重视与支持。

与往年一样,每个队伍有一个team guide。我们的guide是一个阿塞拜疆本地学生,十分热情,还会说一些简单的中文,给我们提供了许多帮助。由于在飞机上有睡眠,我们基本没有被时差影响。

当地的伙食与俄罗斯的类似,每餐主要提供沙拉、米饭、面包、肉、汤和饮料。感觉大部分沙拉和汤味道比较奇怪(咸酸),但是别的食物还是不错的。

巴库是一个漂亮的城市,它被称为风之城市,巴库的风也确实给我们带来了深刻的印象。有两三天,巴库刮起了九级左右的风,有外国选手的眼镜都被吹飞了,所幸我们队的选手没有受到影响。主办方安排了许多旅游项目,基本都是参观当地的名胜古迹。

每天比赛前领队会翻译题目,选手需要上交所有的电子设备。在这里我还想再特别感谢一下领队王宏老师、赵启阳老师为我们每天认真地翻译校对题目,直到凌晨三四点,我们的成绩与他们的努力是分不开的。

回到比赛本身。由于赛前进行了一段时间的集训,我们对ioi赛制还是较为熟悉的。

第一天比赛,我首先阅读了所有题目,感觉rectshoes较为简单,于是从rect开始做起。rect初看没有太多思路,于是猜测答案并不是很大。思考了一下,发现只考虑行或列的情形只需要从小到大加入元素,并考虑极大区间即可。那么二维的情况只需要使用数据结构维护就可以做到带一个log的时间复杂度了。由于是ioi赛制,我直接实现了这个做法,并在一小时左右通过了。

shoes一题感觉是推性质的题目,首先感觉同样大小的鞋子一定是从前往后匹配最优,然后我手画了两个鞋子的所有情况,发现都是把较早出现的鞋子对放前面更优,于是就在九十分钟左右通过了这题。

split一题树的部分分明显只需要考虑割边,但是关于满分做法我一直没有什么思路,于是我决定写一个随机生成树并运行树部分分的做法。实际上,这题的测试数据十分的强。由于是ioi赛制,我试了若干种随机方法,在3h40min左右终于通过了64分。期间和此后,我一直在思考满分做法,但是直到最后也没有想清楚。

最后第一天是第3名,感觉还是比较幸运的,通过split的五名同学大部分都在前面的题目失分了,并且由于数据很强,split用随机获得64分的也只有两名同学。

第二天line是一个提交答案题,vision是一个构造计算机的交互题,walk是一个传统题。初看walk,感觉是一个复杂的数据结构题,就决定先做比较擅长的构造题vision

考虑vision,首先容易想到的是可以先把行列分开考虑,然后统计答案时再合并,那么就是相当于要找一个两个1的数组中两个1的位置差。这个东西一开始我想到的做法是倍增,但是实现之后发现要20000条左右的指令。后来我发现可以直接考虑有多少个gap,即前面后面都有1的位置,那么就只需要实现二进制加一,实现完之后大约需要9000条指令,于是在两小时左右终于通过了。

两小时已经过去了,接下来打算赶紧尝试一下提交答案题line。我首先写了排序之后贪心的一个做法,接下来我感觉单调序列很优,于是打算每次取出一个单调序列作为序,实现之后大概是53分左右。然后我把贪心改成了动态规划,做到了68分左右。接下来写了一个爬山,做到了70分左右。这时三小时过去了,感觉这题的分数已经足够高了,就决定转去做walk

walk一题感觉十分复杂,于是打算从部分分写起。前两档部分分比较简单,而三四两档部分分需要注意到一些性质。写完这些部分分只剩45分钟左右了(由于技术原因比赛延长了15分钟),我开始继续思考walk的最后一个subtask,但是没有什么收获。最后半小时左右我决定回到提交答案题line,发现评分参数最后一档恰好是$n+3$,顿时感觉可能有确定性的做法,于是开始着手考虑,认为螺旋形就可以通过此题。实现完螺旋形之后发现没有获得满分,也没想清楚为什么出问题,还以为是实现错了,在调试中比赛时间就结束了。

最后第二天是第13名,由于第一天分数比较高,所以总共排在第4名。第二天主要失误是提交答案题没有观察评分参数并从满分开始考虑,如果一开始就考虑螺旋形,即使不能获得满分应该也能获得更高的分数。


IOI就这么结束了,虽然有一些小小的遗憾,但是结果还是差强人意的,中国队的表现也已然不错。建议今后的国家队员加强对于ioi赛制和非传统题的训练,也可以多与其他国家的选手交流,以平常心面对比赛。