林凯风ISIJ2018参赛总结2018-07-12 11:17:57阅读量:1118

 
 

这次比赛在俄罗斯喀山举行,前面有数天的Training Tour,最后一天才是最终的比赛。主办方还在活动中增加了一项机器人的比赛。

喀山与北京有5个小时的时差,不过因为在飞机上睡过一觉,也不觉得不舒服。

食堂提供的饭菜大多是午餐肉罐头以及一些叫不出名字的菜。凭着老干妈拌饭护体撑到了最后。

比赛

似乎是翻译的问题,把俄文版的通知翻译过来这个活动就是一个暑期培训班的东西,所以搞了6场模拟赛的东西似乎就说得通了。

第一天是试机,然后7天有6天的Training Tour,一天的机器人比赛。

总体上来说这些题的难度都很适中,掺杂着相当一部分送分题。所以这几场倒比较轻松,而且似乎根本没有反作弊的措施,连网都没有断,后面几场我在监考老师的指导下,用谷歌翻译读题,也省了不少的时间。语言倒已经不是问题的。而且还允许我装Dev-c++。这对于我来说是比国内的全国级别的比赛是方便很多了。

题目大都比较简单,有一些想到正解的题用一些暴力做法也能拿到很高分甚至过掉,有几道没有人过的题目我都是靠着玄学优化骗到了最高分。

这期间也有几道较难的题,像Camel,在网格图中以特定走法构造哈密顿回路,Inhabited mountains线段树维护单调栈,思路复杂了一点,但是赛后想一下,都是可做的。因此,我也对这些题不太在意,轻视比赛的难度。  

最后一天的比赛似乎也是这样的状态,上来就把题目扔谷歌里翻译了。然而看完前两题之后却没有想法,T1 Food delivery是在无向图里找五元环的个数,这题似乎之前见过但是没做过。T2是在在文本编辑器的背景下关于光标移动的最少操作的问题。T3是一道构造题,构造一个最小的正整数使得1n的所有整数都是这个数的子序列,庆幸的是没有SubTask,这说明乱搞可以拿到很高分,只有一些特殊情况会被卡掉。我看着有点思路,就开始对付这题,摸出了一点门道来,搞了74分,幸好这是IOI赛制,我通过二分输入找到了算法的漏洞,补上之后是106分。仍有二十多分错了,但是已经过去两小时了,我看到榜上好几个人过了前两题了。虽然T3没有其他人有超过30分,但是毕竟我没想到做法,倒有点慌。毕竟少点分问题不大,少一题就铁定掉下去了。

T1初看就知道这是枚举点、边,求公共点,公共边,然后去重之类的做法,但是有心无力搞正解,两道不可做在我面前,我只能写暴力。似乎数据是故意构造然后放暴力过的,最朴素的搜索判重给我送了90分。感谢不卡之恩。让我蒙混过关。

T2最初看题的时候倒是个神仙题,怎么像都没有思路,但是榜上过半的满分又令我很怀疑。于是别出心裁写了个水法,暴力维护单调栈在上边瞎跳,随机数据下表现优良。交上去WA了,等我反复调试半天,才发现:题面改了,我在搞T3时有人进来讲过,然而我没在意,就忘了。默默地注释了一大段代码,补上一句输出。过了。剩下二十多分钟。

这几天唯一一场不是因为热而出汗的比赛,尤其惊悚。一边刷新榜单一边盼望结束。然而那个保加利亚的小哥到最后也没翻盘,跟我差了6分而已。

感想

虽然最后混到了Rank1,但是,我真的发现我的见识与技能树跟其他人被差了好多。运气好罢了。要不是最后那一场T1的出题人故意放过暴力,我也只能掉下去了。

另外,对于这几场比赛,我发现IOI赛制对我有很大的帮助,一是过了题能给我信心,二是我也不用写拍(一次都没有),发挥失常的机会较小。

这些题考的全都是思维,没有工业数据结构,高级算法之类。这些题我想到正解或者乱搞出高分都是一种很好的锻炼。虽然对于代码实现的基本功还是要搞好的。

还有就是心态与做题的策略问题,我们的目标是在规定时间内骗到尽量高的分数,虽然最后一场结束以后所有人都认为我不应该先搞T3。到后边只剩两小时做前两题的确比较紧张,但是我还能在完全不知道解法的情况下镇定下来搞完这两题。也许是出于对自己的自信吧。

但是这七八天全是传统题,没有题答或者交互给我乱搞,也是有点遗憾。

还有,除了我之外似乎所有人都会实时关注各大线上赛。有时间就会去打的。或许这就是我跟他们的差距吧。人家初一就能玩遍几乎所有比赛自然有人家的牛逼之处的。

游览

居然还有游览,我们去了两次喀山克林姆林宫,有一次还下了大雨。俄罗斯的雨点好奇怪,开始的时候雨点很疏,但是很重,砸下来的印直径能有3厘米。听说这是冰雹,在风雨中凌乱,还能看到彩虹。还去逛了一圈古建筑,又参观不知道哪个大学。反正好过宅在宿舍了就对了。能出来旅游心情也不错。适逢世界杯,但是我也没有兴趣,一是门票太贵,二是真的无聊。

活动

Training Tour期间有一个机器人比赛,前边有几天的时间自己研究以及听老师讲。然而全然不懂俄语,虽然有人翻译,但是就是听不懂。怪自己英语不好咯。

凭着自己小学对这个东西的记忆,以及老教授手把手的教学。机器人终于会走了。

比赛内容就是让小车在规定路线上走两个地图,完成要求的动作,推杯子什么的。乱搞了一发然后领了个安慰奖。英语很弱,几乎不会交流。

还有一个国际象棋比赛,很高兴帮忙垫底,我对于象棋似乎一窍不通,反正赢了一场自己人,其它全负战绩。


后边几天的晚上有运动,似乎人家都很喜欢踢足球,被逼无奈上去玩了两场。好好的羽毛球不打去跟他们踢球。