写在前面

今年，我有幸作为中国队的一员参加了IOI。对于我来说这场比赛过程尤其曲折，因此最后能得到金牌我感到很幸运。

概述

这次竞赛在哈萨克斯坦阿拉木图市举行。阿拉木图市在哈萨克斯坦南边界上，因此与新疆靠的比较近。可以感受到时差，但对于习惯了在夜晚参加线上竞赛的中国选手来说时差带来的影响比较小。

日程安排上，几个主要活动的前后次序和以前类似：26日是报到日，27 日早上试机下午开幕，28 号和30号是竞赛，29日和31日是游览，1日闭幕，2日返程。

我们比赛和住宿都在Al-Farabi Kazakh NU。这里的食堂供应米饭和通心粉，因此还是吃的惯的。去年在台湾参加完比赛后，沈洋同学曾称“无法感受异国风情”，而今年我认为异国风情是有的，同时又不至于太不习惯，可以说这个地点对我而言是比较理想的。

比赛过程

第一场比赛在28日上午进行。共三道题，boxes, scales, teams。其中scales是交互题。

boxes实际上在7月23日的MUC2015 Contest 2中刚刚出现过(HDU 5303)，在原比赛中也属于简单题。我虽然在比赛的之前没见过这题，但是使用枚举性质多次提交的策略很快解决了这题。这种策略也只能在IOI比赛中使用了，因为只有IOI比赛的每次提交都有feedback，而且失败的提交不会有惩罚，倘若是ACM赛制，尽管有feedback，但是因为罚时的设定，也不能放心的进行多次提交。

scales粗看起来是一道“人类智慧”题。它要求最小化最坏情况下的步数，在题目中却没有给出最优解的步数。但是根据给分的公式和前几次提交的feedback可以推断出最优解为6步。我在构造了一个8步的解后将其优化到了7步。考虑到6步只能提供约9.51bit的信息量，而判别所有情况需要约9.49bit的信息量，允许的冗余部分很小，这对于手构策略来说是相当困难的。因此我放弃了后29分，转而尝试解决teams。实际上，考虑到这个很小的冗余，爆搜策略加剪枝下的有效状态很少，因此最后它还是一个“机器智慧”题。我在最后1 小时想到了爆搜策略的做法，但那时正在搞teams，然后就没有来写scales的满分，这也让我非常遗憾。

teams看似是一个无脑数据结构题，我尝试使用可持久化线段树套可持久化线段树强行模拟点阵状态解决。但是，实际上可持久化线段树的合并复杂度是均摊的而非最坏的，因此最终复杂度是错误的。我在这题只得到了暴力分，还浪费了做scales的时间，赛后觉得非常后悔。实际上，考虑到从点阵中拿点的策略，被拿走的点全部位于一条折线的下方——因此只需要维护折线就可以了。赛后听到这个做法以后我觉得也比较巧妙。

第一试中发生了数据组数过多，测评的等待队列太长的情况，这导致了后半场要等20分钟才能得到feedback。考虑到前年直接没有feedback了，我觉得这种情况还是可以忍受的。

第一试结束后是205分，和近20个人并列在金牌线上，因此二试之前我是比较紧张的。第二场比赛在两天后的同一时间。三道题是horses, sorting和towns，towns是交互题。

我认为sorting是一个相当trivial的题目，注意到可二分性后就是一个大模拟。我在第一个小时内就解决了这个问题。

horses看似是又是无脑线段树，本来想把权值用对数代替避免高精度，后来发现数据规模中有Xi≥2的特殊数据后才发现是暴力扫描log段。这样一来就是一个STL题，相当好写。发现得早，所以在半场时就解决了这个问题。

接下来我就有两个半小时来对付towns了。这个题目和前面的scales类似，也是要最小化询问次数。我在两个小时后得到了一个2N+2N的算法，而标算是2N+1.5N的。我对后一部分加了一个优化，然后居然就通过了。实际上，只加这个优化，步数在最坏情况下还是2N的。1.5N的算法是在2N的算法上加两项优化，而我加上的只是其中一项。因此可以说这个满分受之有愧。

第二试的满分将我从金牌线又往上拉了一段，最后获得了第十名，一个比较好看的名次。

另外，试机也值得一提。练习赛的试题考前是公开的。于是就发生了这么一幕：中国队的四个选手在试机之前讨论了一道题的解法，然后在试机的场上只有一名选手通过这题，同时还是以cheat的方式。这次试机对于我们的信心有一定的打击。

关于游览

第一天上午去了Medeu，大家都知道，比赛的这几天，北京正在与阿拉木图竞争申办冬奥会。这个Medeu就是一个冰雪运动中心。我们乘着这里的缆车到了三千多米的山上。

第一天下午去了一个马戏团，实际上我对于马戏团这种东西并不是很习惯。

第二天的远足地感觉意义不明，不过最后一个小时大家一起跳哈萨克的民族舞蹈这个很有意思。不过总的来看我还是感觉最喜欢去Medeu的那次远足。

关于交流

去年的选手们没有遇到的交流问题在今年出现了。我们的guide，Aida Usmanova，年纪比我们还小，英语口语不比我们几个好多少。这给我们的交流带来了一些障碍。

我们主要还是和美国选手交流——他们四个都有着一个汉语式的姓氏（Chiu不确定，可能是Qiu 的意思）。这就是说，英语交流遇到困难的时候可以切换到汉语。在28日的晚上，美国队和加拿大队组织了一场二十多人的Mafia，加拿大的Ben Zhang担任主持，虽说场上有一半的人会讲中文但是实际上最后还是全程英文。我平时进行英语会话都是一对一的形式，遇到这样十几个人同时讨论的情况就束手无策了。而我们中国队中有三个人扮演的是这个以谎言作为重点的游戏中相当考验口才的Mafia，不消说，最后一败涂地。

在远足的第二天，我们在巴士上和日本队进行了一些交流。今年的日本队中有两名IMO选手，令人影响深刻，尤其是其中的Takaya Yuta，这名选手参加了去年的IOI和今年的IOI，都取得了金牌，而他现在只是高一！不过，中国的四名选手都是高三，这也从一个侧面说明了中国的OI竞赛选手多，竞争性高。

原本我们还想和俄罗斯队，另一个IOI竞赛中的传统强队进行交流，可惜我们仅仅在Farewell Dinner上见到了俄罗斯的两名选手，没有和他们全队进行合影。

韩国队是今年杀出来的一匹黑马，韩国的Yoon Jeehak是今年唯一的满分。但很可惜，我们和韩国队的选手仅仅在Mafia的那个晚上有一面之缘。

我在Medeu的缆车上还遇到了菲律宾队的Leader，Martin Gomez，他的汉语讲的十分流畅，说是在上海住过几年。我们在第二次远足的时候又遇到了Gomez，他和两个选手在一起，据说这两个选手对于来中国读大学很感兴趣，我猜他们就是菲律宾队中那两个有着汉语拼音姓氏的选手了。

感想

今年的六个试题中有两道交互题，而没有提交答案题。我觉得我们中国的OI也应当注意这一点。这并不是说每场大型比赛都一定要有一道交互题，就像现在提交答案题的地位一样，而是说，我们至少要有测评这类试题的能力。我使用过cena和lemon两种主流测评软件，它们都只能测传统题和提交答案题。也就是说，在日常训练中难以进行交互题的训练。

我们知道，现在OI界有一个术语叫做“卡常数”，它可以表达两种意思——一个复杂度正确的程序由于常数问题被卡掉，或是一个复杂度错误的程序由于常数小卡着时限通过了。OI是思维的训练，我认为存在这种由于个人代码风格而导致的区别是不好的。这次IOI给了我启发——以towns为例，3.5N也是O(N)，4N也是O(N)，这个要说是卡常数，也可以，因为就是要想方设法减小常数吗！但是这个减小常数的过程就相当考验思维了，不像TL这样，有机器依赖性，给人以玄学的感觉。我觉得交互题限制调用次数是一个很好的发展方向。

另外，我们知道IOI的考纲内容少，NOI的内容多。考纲内容多，就会出现考知识而不是考思维的现象（“模板题”）；考纲内容少，就会更注重思维上的难度。就我自己的感觉来说，我觉得独立想出towns的3.5N算法比写一个带垃圾回收的可持久化树套树更加有成就感。我觉得，我们的OI应当向低考纲高思维难度的方向发展。我感觉交互题就是一种很好的载体。（尽管我的集训队论文已经给某省带来了一股不正之风）

IOI结束了。我的OI生涯也结束了。但这不是结束。这甚至不是结束的开始。这只是开始的结束。大学生活即将开始，我将在一个新的地方开始新的生活！