很荣幸成为中国队的一员参加第 35 届国际信息学奥林匹克竞赛,感谢CCF和科协组织参加比赛,感谢领队老师们帮助鼓励我们和为我们翻译题目,也感谢主办方对比赛周到的组织安排。

本次比赛在匈牙利塞格德举办。这个城市不大,建筑风格比较古典,基本没有什么高楼。入住的酒店环境还可以,只是房间有点小。这里的餐食和国内差异比较大,很多饭菜都比较咸,且有些没见过的菜品。组委会为每个队伍都安排了一个guide,主要负责向导和传达主办方安排的工作,为我们提供了很大的帮助。

因为各种原因,去程比较漫长。北京时间凌晨四点多就要起床去机场,中途从宁波转机,抵达时已经到了当地时间晚上七点多。接着在布达佩斯机场又经过了两个小时的等待,乘坐巴士前往了了塞格德。到达酒店时,已经到了第二天凌晨。

比赛在一个体育馆里进行。练习赛的五个题目和网络赛的一样,由于只有两个小时,我写完并通过了前四题。下午是开幕式,开幕式表演了当地的特色舞蹈,也介绍了冯▪诺依曼以及其他几位匈牙利杰出的科学家。

第一天比赛进行的还比较顺利。开场先看了T1,大概10分钟后想出了做法,然后花了大约一个小时的时间写出并完成了调试,过掉了这题。紧接着是T2,一道交互题。题目性质给出的提示也比较明显,大约三十分钟内写出了一个比较直接的解法:每次选三个链端询问,并缩其中两个链。获得了85分。接下来我尝试了若干种优化方法,并通过策略 “如果有确定两个点间没有边则选的三个点中必须包含这两个点”,节省了该情况下的操作次数(只需询问一次),获得了满分。最后是T3,首先我写了一个 O(n^3) 的 dp,状态为矩形的上下端点i,j 以及一个贯穿矩形的列 p。然后发现其中 j 这一维可以被优化掉,直接使用满足 (i,p) 最大的 j,得到一个 O(n^2) 的 dp,如果算上排序复杂度也仅 O(n^2 logn) ,交上去后WA了几发,但通过对拍发现了是转移顺序没有处理好,在3小时 20分钟左右的时候过掉了这题。在剩余的时间里,我读了读附带的cpp reference以及machine environment文档。

两场比赛之间的一天,我们去了Ópusztaszer公园。先参观了一个匈牙利的历史博物馆,又去体会了一些当地的民俗、文化,下午还观看了一场马术表演。

比赛到了第二天。由于第一天没有签到题,我误判了该天T1的难度,认为其结论可能比较容易得出。我推出了一组必要的条件,错误的认为其是充要的,并写出了其一个O(nlogn) 的实现。但测完样例后发现过不了最后一个样例。我手推了一遍发现该条件确实不是充分的。此时我有些紧张,去做了T2。发现T2的 O(n^2+nq) 做法比较简单,我就先写了出来,得了65分。我发现可以进一步优化,写了个O((n^2+q)log^2 n) 的解法,但交上去之后发现TLE了,仍然是65分。此时时间仅剩不到两个小时了。由于我此时T1的得分很少,且有一些可以接受平方、三方的部分分,我又回过头去思考T1。但最终仅仅多推出了若干个必要条件,始终没有想出充要条件。在最后的一个小时中,我简单地写了几档T3的暴力,回去给T2进行了常数优化,但最终仍没有通过。

第二天感觉完全没有打好,拿到任何一个有难度价值的分数。简单反思了一下,主要原因还是因为被T1耽误的时间太多了,导致后面的题目时间不够用,且心态较紧张,不利于发挥。特别是T3有着一些比较明显的Partial做法,而我为了赶时间仅打了几个特殊性质的暴力,且T1的暴力也没打全。另外就是T2,当时也是为了“省事”写了一个2log的算法。但赛后重新思考了一下,1log的算法也不是那么难想、难写,而且不太用担心超时等问题,可能这是一个更优的选择。总之,这天我对题目的时间分配很不合理,且错误地评判了题目的难度,导致最后没有一个题得到满意的结果。

第二天比赛后,我们又去了Makó参加了一些玩乐项目,并在下午参观了Vadaspark动物园。晚上大家还去参加了Culture Night 活动,体验了匈牙利当地的舞蹈,不同国家的选手们还上台演唱,该活动一直进行到了午夜。

接下来的一天,我们上午去了塞格德的市中心,下午是闭幕式,同时举行了颁奖仪式。最终我两天总分排名第6。对于第二天肯定有一些遗憾,如果能够合理地分配时间,无论在任意一题上突破都能够将排名有所提升。

此外,在活动进行期间,我们也和一些外国选手进行了交流,其中也有很多华裔选手。在比赛空闲时间,我们去了赞助商Jane Street 提供的活动场所Jane Street Hub,玩了一些桌游。我和一些外国选手也互换了小礼品。

虽然略有遗憾,但这次IOI是我人生中一次难忘的经历。希望今后的中国队训练中能够汲取往年参赛的经验及教训,取得更加优异的成绩!