摩洛哥/马拉喀什· 2015年5月21日

ICPC 世界总决赛2015

第二次参加总决赛，做完了所有简单题，略有遗憾。

鉴于去年的表现实在是太拉了，这一年我们决定好好准备。

队内三人分工已经十分明确。我是负责代码题和各种花里胡哨算法的人，于是在这一年里我学了非常多的算法，有很多是以前听都没听说过的，比如半平面交，AC自动机，看名字就觉得花里胡哨的，但是很常用。我个人的训练方式就是刷往年的地区预选赛的题，这样基本就能覆盖所有常用的算法了。

然后另一个码题的队友负责数学，动态规划，贪心等问题。总之但凡跟数学沾点边，就是他的问题。他的训练方式就是在Codeforces和Topcoder上打比赛。这两者上面的题目风格跟ICPC的题目风格差别还是非常大的，每道题或多或少都跟数学沾边，而且因为比赛时长的缘故，代码量还不能特别大，所以正适合用来学习这方面的算法知识。

最后一个完全不码题的队友负责花里胡哨。我们对他的要求是，你不用会码，但是你啥都得会，得有见识。他的训练方法就是打开一个在线评测系统，然后按顺序一道一道看题，不会就看题解，遇到了什么花里胡哨的，就记住，有必要让我们知道的，就告诉我们。

除去个人训练，我们团队训练也比去年多了不知道多少倍。为了好好准备比赛，我们最后一个学期（我和数学队友是研一，看题队友是大四）全都选了下限的课，还是水课，就是为了把更多的时间用来训练。一开始大概一周一练，后来临近学期末一周两练，等到放假之后，直接一天一练。要知道，一场比赛5个小时，加上之后把可做的题目都补上做完，这一天就过去了，而且可能还不够。

然后在训练的过程中，我们逐渐树立了爆棚的自信心。我们在Codeforces上练5个小时的模拟赛，我们发现今年参赛的不少队伍，都在跟我们练一样的比赛（可以任意时间开始虚拟比赛，所以不是同一时间）。当时的清华队，北大队，上交队，还有一些欧洲队，我们都遇到过。而打的比赛多了，自然就有失手的时候。我的意思是说，这些强队都有失手的时候，于是我们几乎把能见到的队都赢过一遍。最终得出结论：只要运气和状态足够好，还有什么队是我们完全赢不了的么。思来想去，就只有今年的tourist队了。我们今年的目标就是拿牌。

而最终的事实证明，“只要运气和状态足够好”这个前提条件还是太苛刻了。最终正赛的时候，我们也就发挥了正常偏下的水平而已。

而更严重的问题是，我们在Codeforces上练的训练赛大都是俄罗斯训练营的比赛（俄罗斯都是超强队，例如圣彼得堡大学ITMO，也就是tourist所在的学校，都已经霸占冠军好多次了），而这些训练营的题目风格跟总决赛差距很大。这里的风格更接近于Codeforces本体，就是数学比重很高，而代码量要求很小。简而言之，可能这些比赛全都练我队友了，我自己码纯代码题的能力完全没有得到锻炼。而很不幸的是，我是在这次比赛的赛后总结，才终于意识到了这个问题。

今年我们三个人，外加领队，以及去年没法去俄罗斯的副领队，全都一起赶飞机来到了摩洛哥。比赛前几天的旅游活动，我已经没什么印象了，当时大概所有的心思都用在想比赛上了。

主要就记得当时室外超级热，出门就想死，只想待在空调房里。路上遇到热情群众，看你热，就主动跟你搭话说热。然后他唔噜唔噜说了什么我也听不懂，最后指着远方来了一句：“the great Sahara”！就这句我听懂了，应该是在炫耀附近有撒哈拉沙漠。

有一件令我印象深刻的事，这位拥有俄罗斯血统的副领队，是真的很虎。我们在马拉喀什市中心的集市中，遇到了一个摆地摊的纹身师傅。别问我为什么纹身师傅可以摆地摊，反正一眼看上去就不靠谱，不像什么正经生意。然后这位副领队就突发奇想，要不我在手臂上纹个老虎吧！然后纹身师傅让他画下来，他就在手臂上画了个Q版的猫。

我们三个人当时想法极其一致。这个纹身你要是做了，你的手还要不要了…最终，不知道出于什么原因，副领队并没有纹。也许是他最后终于也发现这玩意不靠谱了吧。

集市上还有人卖鲜榨的橙汁。榨果汁的机器一看就很浪费。首先你把橙子从中间切两半，变成两个半球。然后把一个背对着放到机器里，然后手动压扁，橙汁就出来了，然后这半片橙子就报废了。肉眼可见的，浪费率极高。不过有一说一，这橙汁真好喝。可能就是因为浪费得多，导致橙子皮，包括里面的果肉皮一点都没进果汁，所以完全不苦，纯甜。

我以前没见过这种机器。不过几年之后，在我回国的时候，在机场再一次见到了这种手艺。那是一个纯自动的机器，跟自动贩卖机一模一样。你交钱，它就用同上的方法，自动现场切三个橙子，压扁榨出果汁。结果那个机器显然精度不行，中途卡住了，偷了我一个橙子，导致我那杯只有三分之二，不过我显然是没处说理了。而再过几年我再回国的时候，就再也没见过这种机器了。大概是成本太高，机器质量太差，而投诉又多，直接倒闭了吧。

言归正传。我们三人讨论了一下，要不要在现场来个模拟赛。最终放弃了，觉得太蛋疼了。这么临阵磨枪也不知道意义是啥。

正式比赛日。我们来到现场发现，有13个颜色的气球。也就是说，这次有13道题。这也是史无前例了。按道理来说，应该会有一道超级大水题，白送分。而结果确实如此。

开场5分钟，有人过了A。一看果然送分题，跟上11分钟通过。

然后就是找下一题。我们发现B是个几何题，一看就不可做，直接撕了。然后F和M是两个代码题，应该没什么难度，但是需要时间。D一眼看上去像是个需要微积分的数学题。然后读题队友发现，C是个简单网络流。我看了一遍发现没问题，直接开码。

然后在28，29，30分钟，连续有人通过了F，C和D。我们更加确定C就是简单网络流。在35分钟码完了，提交，错了。尴尬了。我看了两遍代码，没发现错误，于是卡题了。

这个时候，我们决定让读题队友debug，我开始码F，数学队友开始推导D题的公式。然后在一个小时左右的时候，读题队友发现C题漏情况了。于是把这个情况加上，修改代码，63分钟提交通过。

然后F我可能码了半个多小时，然后照着样例调代码又调了二十分钟，只能说代码能力还是太差了。最终在93分钟提交，错误。然后打印代码，离线debug。

数学队友开始写D。因为他之前基本没写过几何题，我跟他说圆周率常数一定要写得足够长（我被这个坑过），然后没有时间复杂度要求的全用long double，不要用double。这期间，我发现了F的问题，占用了一点时间修改，然后102分钟的时候通过了F。

在112分钟的时候，D一遍通过。

而这个时候，我们4题，抬头一看榜，已经天翻地覆了。39，47，53分钟，有人通过了L，J，I。115和118分钟，有人通过了E和H。这个时候，全场有9题有人通过，而榜一大哥，我记得是东京大学，已经7题了。两个小时7题也是史无前例。按照之前CMU教练的分析，2个小时有9题有人通过，这种情况想要拿牌得10题，金牌要12题。

这个时候，数学队友开始看L，我开始码I。I就是个很简单的线段合并。有很多组线段，你要计算出被所有组线段都覆盖的区间总长度。我们当时第一想法就是用线段树，还得是离散的线段树，因为端点都是实数。但是这怎么想都不合理，因为现场已经很多人通过这道题了，难道大家都用的离散化线段树？我们转念一想，是总决赛，还是有可能的。不过最终证明是我们想多了。这题直接把所有空白部分变成线段，就变成了求至少被一个线段覆盖的区间，然后你用总区间减掉这个就行了，一个排序搞定。

然后我们就在现场开始纠结这个离散化线段树，说实话真的不是特别复杂。我们在126分钟就完成了第一次错误提交。因为我们从来也没写过，想想也知道，各种边界条件，实数相等的判定，很容易出问题，于是就开始了漫长的debug。这个题是卡了我们最久，浪费时间最长的题目。我们大概每半个小时交一次，最终错了四次，在第269分钟终于艰难地通过了这道题目。这题从开始做到最终通过，用时怕是超过3个小时。

在离线调I的过程中，数学队友开始写L。不是特别复杂的题目，173分钟一次通过。

然后就是这次比赛最神奇的题目J。看着像数学题。数学队友看完之后问我们，你们知道有什么能快速计算两个大整数相乘的算法么。我们都说不知道。其实就是快速傅立叶变换（FFT）。我们训练的时候完全没遇到过FFT的题目，所以没人会。而数学队友准确地找到了算法，就差一个FFT。那怎么办呢？交表吧。

我们看了一下，这个题输入就一个整数，正适合交表，询问部分可以看表回答，不用管。然后我们掐指一算，这个表简直能写下。不同的精度下，需要的文件大小不一样。比如如果我们每100个数存一个，那我们需要上交一个100kb大小的程序，代价是如果询问问到中间的数，你需要把这100个全都算出来。如果每50个数存一个，就要上交200kb，但是程序运行时就只需要算50个数的时间了。我们也不知道比赛允许上传的文件最大是多少，所以决定不管了，先试试看。

然后我们就开始了漫长的跟表的战斗。本来不用这么麻烦的，但是怎奈比赛用的笔记本性能实在是太差了。一个100kb的文件，我队友按了一下保存，直接就卡住了，差点死机。这光标转圈转了整整30秒，终于保存完毕了。每次保存都能吓死个人，生怕它死机。而我们必须要小心翼翼地操作，一旦复制粘贴的数据太大了，怕是又要死机。而本来写程序写一点保存一点是好习惯，现在完全变成了负担。每次没改完的时候，我队友顺手一个快捷键保存，然后就会紧跟着一句国骂，为啥又手贱了。

接下来比赛的两个小时，基本上都是，我调一会离散化线段树，队友调一会这个巨大的表，我们轮流操作，轮流提交，轮流错。

在封榜之前，奖牌区要求的最少题数已经来到了8题。而那时我们连卡2题，还不知道咋办呢。因为我们的目标是拿牌，所以一定要开新题。所以在我和数学队友忙活的时候，读题队友就去开新题了。他觉得E可做，就是个简单贪心。然后我就迅速写了个简单贪心，然后就错了，连错两次。然后他也不知道怎么办了，不知道是算法问题还是程序问题。这下连卡三题了。然后数学队友来看了一眼，说这贪心肯定不对啊，然后30秒给了个反例。然后这题彻底不会了，我们又回到了卡两题的阶段。

这个交表的J题，在比赛结束前的四分钟最后一次提交，艰难通过。至此，我们的比赛结束了。

唯一值得一提的是，我们J题是交表，而我们是全场唯一一个交表队。在官方提供的赛后总结里，专门提到了，这个题可以交表，而裁判们发现，现场真的有一个队交表，那个队就是我们。

我当时觉得，是不是命题人压根也没想到这题还能交表，是因为我们交表了，他们才意识到可以，然后把那段话加到了总结里。直到十年之后，我自己成为了裁判，凭我跟他们的接触，以及我们对题目准备的要求来看，极大概率当时裁判早就知道这题可以交表，但是还是允许了这个操作。

我们最终的成绩是7题，去掉罚时并列28名。算罚时50名整，所有七题队倒数第一。

赛后我们跟领队说的就是，我们做完了所有简单题，算是完成任务了。而因为I和J实在是卡了我们太长时间，我们完全没有时间做别的题了。如果I脑子不抽，J我们会FFT，每个题都能省下至少一个小时的时间。那样的话，M这种纯代码题，还是有可能出的。H这种纯数学题，数学队友能做出来的概率还是很大的。

但是现实没有如果，只能说，略有遗憾吧。恭喜ITMO的tourist队完成退场成就，以满分的成绩拿到冠军，成为有史以来第一个也是唯一一个在总决赛退场的队伍。揭榜的时候全场沸腾，看来大家也都想目睹传奇的诞生。