叶卡捷琳堡

这是我第一次参加ICPC World Finals，心情十分激动。这个时候它甚至还叫ACM-ICPC World Finals。

比赛的晋级之路这里就不赘述了。年年都是在密歇根州的大急流城，详情可以参考预选赛总集篇。

这里我不禁想提一下，俄罗斯的签证是真的难办。在我去过的这么多的国家里，它的签证算是最难办的那一档。它要求你提交活动官方提供的邀请函，要原件。且不说这个活动官方得首先有资格提供这个邀请函，就是这个国际快递也够你喝一壶的。那个邀请函看起来非常正规，不是什么随便一个文档然后校长签个字就完事了的那种。它用的看上去是一种特殊的棕黄色纸张，上面都是看不懂的文字，有序列号，有你的名字，有签字，有盖章。然后这个东西要漂洋过海，国际快递从俄罗斯来到美国。别问我寄丢了怎么办，建议直接放弃。然后我们找了个旅行社来帮我们代办这个签证顺便订票。印象中这个签证直接收了我们每人三百多刀。还好有学校报销。

今年比赛之前，我人在中国，两个队友都在美国，基本没有训练。我们尝试了两次在线的训练，一边开视频会议，一边打码。结果就是，完全扯淡，毫无训练痕迹。在我回国之前，因为各自学业繁忙，我们全队只练过很少的几次，剩下的都是各练各的。用流行的话说，这叫裸考。

这次总决赛之旅从请假开始。我是万万没想到有朝一日会需要在大学里请假，而请假居然可以这么麻烦。

我在上海交通大学密西根学院，参加的是2+2的项目。大学前两年在交大，后两年在密西根，最后一个学期回交大参加毕设，然后能拿到两边的毕业证。你也可以不回交大参加毕设，这样你只能拿到密西根大学的毕业证。实际上，很多人都选择不回交大毕业，因为如果最终你要留在美国工作的话，回交大毕业几乎毫无意义，还不如用这个学期的时间在美国多参加一次实习，对找工作来说效果显然更好。这就直接导致了我们学院的毕业率一直极低，我印象中（大概不太准确）不到80%，几乎铁定是全交大垫底。

而现在的我正好就在交大参加最后一个学期的毕设。因为我的学分已经够了，所以这个学期只有毕设，没有其他的课。而我之所以选择回交大毕业，也是因为确实没想好以后到底要在哪里发展，所以还是先把两边的毕业证都搞到再说。话虽这么说，其实还是极大概率要在美国工作。于是我的心态其实极其放松，就算毕不了业，我也无所谓，就当回国跟同学玩一个暑假了。

背景介绍完毕。然后就到了要比赛的日子。众所周知，在大学你可以随便翘课。这不只是中国大学的传统，全世界大部分大学只怕都是这样。我在密西根大学也很少有教授喜欢点名的。而让我万万没想到的是，在一个可以随便翘课的环境下，请假好像成了十恶不赦的事情。

首先是为什么需要请假。本来我也没想请假，反正就一周两节课，直接翘课就行了。但是好巧不巧那周刚好是毕设第二次答辩，占最终总成绩的5%。当然，这点分我也不在乎，反正及格肯定是没问题。但是当我跟导师老大（毕设有好几个导师，其中的头）说的时候，他直接说，你不能不参加，任何一次答辩不参加毕设直接挂科。

然后我就震惊了。这5%的分凭什么就挂科了？翻遍整个课程的介绍、评分详解之类的所有文件，没有任何地方提及不参加其中一次答辩就挂科的事情。如果是最终答辩也就算了，但是这才第二次，后面还有两次呢。我完全不理解，这位导师为什么要做出这样的决定。以我浅薄的见识，我只能认为是我挑战了他浅薄的面皮。

我十分无语，只能说，我参加的这个比赛十分重要，是世界总决赛。如果我能正式请假，能放我过么。他说，如果是正式请假可以考虑。没办法，只能去请假了。

然后就是去找指导员请假。我已经不记得最终需要多少人签字了，好像是三个？但是首先需要得到指导员的认可和签字。然后我跟指导员说我要请假，去参加这个比赛。然后指导员的态度虽然比导师缓和很多，但是总体思路跟导师一样。大概就是，为啥要请假，毕设很重要，非去不可么，之类的话。然后我的态度很坚决，非去不可。主要是，上面我也说过了，我其实并不在乎这张上海交通大学的毕业证，对我来说大概率啥用没有，不要也罢。当然我没有这么说，但是这导致我明面上的态度非常坚决：非去不可。

指导员大概是见到我的态度非常坚决，以及我前两年在交大的时候以全学院第二的学分绩拿到了学术成就奖，“我是一个好学生”的结论深入人心，这才使得他最终松口，同意我请假。最后他跟我说，好好比，为校争光。

然而，我是代表密西根大学参赛的。上海交通大学校队那么强，哪里用得着我啊，而且我哪进得去啊。不过我显然没说。不知道他要是知道我都不是代表交大参赛，会是什么感想。

最终我请到了假，拿到了大人物的签字，然后去跟导师商量，导师最终同意只扣我5%的分，就不挂我的课了。

实在是太不容易了。作为一个I人，我感觉请这一次假把我这一年的社交份额都用掉了。

然后在没有后顾之忧，去参赛！

我从上海出发，只有我一个人。我的队友以及领队都是从美国出发。我上面也说过了，有很多人选择不在交大毕业，而用这个时间在美国实习。我其中一个队友就是这样。他的实习是标准的美国科技公司暑期实习，12个星期整。而总共就12个星期，他要请一整个星期的假，大概也是非常不容易的。在他的描述中，我也听到了“非请不可”之类的话。最终大概也是排除了千难万险，冒着拿不到最终offer的风险，拿到了这一周的假。

我的飞机要在莫斯科转机。倒不如说，你要飞俄罗斯的任何地方，大概率都要在莫斯科转机。转机过程还算流畅。只是在海关的时候，那人问我去哪，我说Yekaterinburg，他说Екатеринбург？我说Yekaterinburg。他说Екатеринбург？然后我俩就循环了。

我的写法就是当时实际发生的情况。我说的是英语，他大部分说的是英语，但是城市名用的俄语发音。而叶卡捷琳堡的俄语发音跟英语发音差别有点大，尤其是重音位置。我反正是没理解他说的是啥。

最终他好像是理解了我说的是啥，就让我过了。

顺利到达叶卡捷琳堡。然后到了宾馆，跟队友会合，然后我们仨人集体傻眼了。没人有转接头。

我们仨人虽然不是第一次出国（显然之前都去过美国），但是这次情况还是不太一样，毕竟美国要长期生活，转接头无论如何都要买。而这次大概是我们仨人第一次到一个真正需要转接头的国家，没一个人想着要带。

然后我们派了个代表，也就是我，去前台问有没有转接头可以借我们用用。然而当时的我英语也不好。当我先后说出了，socket，power，charger之类的词之后，前台笑着跟我说，我猜你想要的是adapter。说实话，我不知道adapter是啥，但是听着就像我要的东西。

然后我得到了一个转接头。然后我们全队三个人在这之后的一周，每天都聚在一个房间里，轮流充电。

我已经不记得那些天都干了啥了。我印象中，领队带我们去了城里的一些景点。但是具体是什么景点，完全没印象了。我们队里没有人懂俄语。其实我们队的副领队原来好像是俄罗斯人，但是出于某些原因去了美国。根据他自己的说法，他如果再次进入俄罗斯，就很难再出来了。他个人表述得很委婉，但是我理解下来大概就是这个意思。如果他在的话，也许我们能玩更多的地方吧。

然后终于来到了比赛日。这次的总决赛题目难度实属灾难级别。有谣言声称，是因为裁判们（也就是命题人）害怕tourist（世界排名第一的竞赛选手）会退场（就是比赛没结束就做完了所有题目），于是把题出得特别难。要知道在前一年，他的队伍差一点点就退场了。根据官方出的赛后总结，最难的一个题在临上场之前加了三个极端数据。如果没有那三个数据，他去年就已经退场了。

总而言之，不论谣言的真假，不论为什么题目这么难，这次的题目实属灾难级别。很久之后，当我自己成为了总决赛的裁判，知道了题目选择规则之后，我就更加无法理解这一年到底发生了什么。我问了很多当事人，他们都说：“那一年有什么特别的么，不记得了”。也就是说，那个谣言大概是扯淡的了，而在裁判心中，这只是一次普通的总决赛，无任何特别之处，仅仅只是题目难度翻车了而已。

说回比赛。

全场首杀K题来自17分钟。当比赛进行到15分钟，我们就已经发现不对劲了。往年的比赛首杀十分钟上下肯定出了，结果这次到15分钟还是全场静默。而当首杀出现之后，情况并没有好转，反而更加恶劣。正常情况下，首杀之后，那个题肯定是所有的队都在跟，一个小时的时候就已经大几十个队伍通过了。结果这次完全不是，几乎没人跟。而我们读了K，发现完全不会做，当即就沉默了。我们都认为这是一个数据结构题，但是我们都没看出来这题要怎么用数据结构。随便写了点优化，全场错了八次，也没能通过这道题目。这个题需要用到区间最值查询（RMQ）算法。然而我们队当时菜到，这么基础的算法都只是听说过，没人精通。于是硬是没人想到要这么做。

僵持的局面来到了第28分钟，有人通过了D题。然后我们读了D题，觉得可能可做。之前读的时候并不确定这题能不能做，因为这题也不是一眼看上去的水题，不过既然有人过了，那说明肯定可做。然后我的一个队友就去研究D了。然后一个小时之后，我们通过了D题。这是我们本场比赛通过的第一题。

第35分钟，有人通过了C题。C是个计算几何题，一眼看上去就是可做，但是情况特别多，很难通过的那种。我们全队都是计算几何菜鸟，遇到几何题都是我直接上去莽的。结果就是，果然这题情况特别多，一直到比赛结束，交了6次都没能通过这道题。本来我们以为，我们距离正解已经不远了，然而赛后我们从网上下载了我们的程序和官方数据一测发现，我们还差十万八千里。这题计算过程中全是实数，而最终的输出要求整数，这对计算几何精度的理解要求很高。在计算结果无限接近一个整数的时候，不同情况下，你要向上取整，向下取整，或者是近似，需要严格分类讨论。而我们三个计算几何小白肯定是不懂这个的。这题没有任何可能性通过。

第68分钟，有人通过了I题。我们读了I题，发现不会做。但是这次不一样。我们一看通过的学校，这是什么菜鸡学校，这也能通过I题？然后根据我们的经验，这题大概率可以瞎搞。我们也没想出什么有效的瞎搞方式，最终只能采用最暴力的方法：搜索+卡时。也就是说，程序只做暴力搜索，然后当它快要跑到时限的时候，直接退出并输出当前最优解，有啥输出啥。事实证明，这么做是对的。为了保险起见，我们在处理之前还随机打乱了数据的顺序，以防命题人以这种方式搞我们。我们前四次提交都是因为卡时范围没设好，提前过早退出之类的原因错了，调了一些参数之后，第五次提交，终于通过了I题。而最终结果证明，首杀I题的确实是菜鸡学校。他们全场只通过了这一道题。这在总决赛历史上只怕是前无古人后无来者，足以名垂青史了。

其他的有人通过的题目就跟我们没有关系了，看了题之后，主打一个，一看一个不吱声。

B题我们看完之后就知道，肯定是个背包动态规划，而且是需要那个多重背包优化的。而我们没人记得那个优化怎么做了。而事实上，这个题不只需要多重背包优化，你需要在那个优化思路的基础上，继续推导公式，做出新的优化公式。显然我们是没有这个能力了。

E题是最可惜的，我们看完之后完全没思路。而事实上，整个题目的逻辑跟有限状态自动机（DFA）的化简方式一模一样。而我和一个队友一年半以前才一起在课上学过，结果俩人愣是没一个人想起来。本来这题是天赐良机的，结果不知道为什么，比赛现场没想出来要怎么做。

我们还尝试做了A题。A题一直到比赛结束都没有人通过，包括场外队。我们之所以会尝试，主要也是比赛的时候，啥也不会，实在也是没事干。而这个题就是瞎搞的题目，跟算法没什么关系。于是我队友从比赛中期开始就一直在想这个题，一直到比赛结束想了三个小时，交了两次，没能通过这道题目。赛后领队还问我们，你们的提交是认真的么。我们回答是。而这个题其实确实可做，现场的队伍完全是被没人通过的积分榜给吓住了。赛后有人问过裁判，裁判们一度认为，这个题是全场最简单的题目，应该被首杀然后大面积通过。只能说，如此巨大的误判，也是史无前例了。而事实上，这个题对于n模4的余数，有四种情况，四种情况的最优解都是n。我队友已经成功地推演出了其中的三种情况，就差最后一种，只能算到n+1。只能说是非常可惜了，痛失总决赛首杀，甚至是唯一杀的机会。

最终我们两题结束了这次比赛。

我们能感觉到，赛后大家都很无语。总决赛题目难成这样也是史无前例的，而那个为了防止tourist退场的谣言因此很快就传开了。场外tourist队以七题、更低的罚时成绩拿到第一。当然场外队是不算的。他们其实差点就能八题甚至更多了。A题他们有个人想了一个小时，最终没想出来，可见确实不是大水题。然后J题就十分巧妙了，这题一看就大概知道方向，但是推导细节会让人想死，外加代码量超级巨大。根据Petr的博客，现场发生了“我码完了，我去…我忘了要字典序最小了…我放弃了…”的情况。

最终揭榜的时候，出现了戏剧性的惊天大逆转。封榜之前，莫斯科国立大学以6题的成绩遥遥领先，第二名只有4题。这种局面，加之这次的题目难度，怎么看他们夺冠都是板上钉钉了。结果圣彼得堡大学最后一个小时通过了三题，同样是7题，以39分钟的罚时优势完成惊天大逆转。最后一题8次错误提交，正确提交出现在比赛倒数第二分钟，也是非常极限了。

排除这些小花絮，我们全队都很沮丧，然后一致决定明年再战。