月亮岛

作者：楼天城
人称：楼教主

OJ惯用昵称：ACRush
大学：清华大学

         2007年ACM-ICPC全球总决赛:第二        
         2009年ACM-ICPC全球总决赛:以9道题目，在与第一名ac相同题目数，因罚时上森彼得森堡大学少于清华大学，屈居第二
         抵达瑞典的当天晚上，我们就体会到了北欧的高纬度特色，晚上十点钟时天空仍然是亮的，据当地人说，到了夏至日前后，每天太阳只落山3个小时左右。
         瑞典之旅的前两天以游玩为主，练习赛（试机）安排在第三天，练习赛前，我们深刻体会到了瑞典的第二个特点——冷。赛会要求所有选手身穿ICPC的t-shirt参加比赛，并且还强制要求最外面的一件衣服是ICPC的t-shirt。Bill大叔一如既往地热情，在露天广场讲演了30分钟，不过在近似0度的室外，虽然t-shirt内套有毛衣，但是也很难抵挡刺骨的寒风。
         练习赛过程中，我们比较低调（也可以认为是低靡），最简单的题目A在最后时刻才AC（记得后一天，一名外国选手还特地关于此事对我们表示担心，我们其实是想留下一道题目来测试）。参加这么多场ACM以来，我对练习赛有如下几点体会：
        (1)     练习赛的最重要的作用——试机
练习赛往往使用特别简单的题目，选手可以选择比拼手速，看看能否排在前列。记得MobileRobot成功在东京总决赛前的练习赛排在第一；也可以不着急做题目，先花一些时间适应比赛机器环境。
        (2)     练习赛中可以测试Judge的习惯
比如我们发现此次Final测试中Wrong Answer的优先级比Run Time Error高一些，不知道有没有其他队伍注意到，:P。
        (3)     练习赛中可以测试一些重要参数
比如今年就有两个发现，首先，提交系统中的编译指令没有添加-O2优化；其次，提交系统的C语言运行堆栈大小是8MB。
         无论是出发前，还是在瑞典，许多同学和老师都看好Proxima，谢谢大家的关心。但是直到赛前，我们的精神状态都没有调整到最好。我由于赛前参加TopCoder个人比赛投入了大量精力，略微影响了组队比赛的感觉。另外，zzy比赛前一周精神状态也不是很好，至少我能感觉得到。
         不过，赛前晚上我们休息得很好，比赛在上午10点左右拉开序幕。下面分享一下比赛的过程吧。
         13分钟，A：二分答案，然后枚举或者动态规划。1Y
         A题虽然n的范围只有8，但是如果枚举8!=40320种情况的话还是时间略微有一些紧，所以我们使用了比较稳妥的动态规划方法，这样计算量只有2^8=256。
         A成功1Y之后排在第4，当时看来起步很顺利。
         尝试了2次E，结果都是WA。
         我们都没有想到一场悲剧已经拉开序幕。E题是此次总决赛之旅的最大败笔，这个第二个开始写的题目结果是倒数第二个通过的。
         103分钟，B：枚举错误的门，通过逻辑计算判断是否满足。3Y
         这题是zzy写的，主要是由于题目很琐碎，而且我被E卡住了。在过了A后的长达100分钟左右的时间中我一直在E中苦苦挣扎，可见当时的状态真的很差。
         114分钟，F：计算几何。2Y
         这题是zzy写的，至于出错一次的原因我也不很清楚。
         121分钟，D：计算几何，判断包含4个圆的最小圆。1Y
         其实我在此次总决赛过程中，除了E题之外都挺顺利的，D题其实有很简单的算法，远比Petr提出的方法简单，至少可以从7分钟写完就可以看出来，大家自己想一下吧，:P。
         至于开D题，有一个很扯淡的原因，当时zhouyuan起身看气球的情况，发现粉色气球很多，于是他回头看了一下气球颜色和题号的对照表，便告诉我D题有很多队通过，于是我毫不犹豫就做了。结果7分钟后1Y了，志愿者送来了一只颜色很神奇的气球，太赞了!
         短暂的20分钟通过3题之后，排名已经好看了许多，好象是第3吧？但是E的阴影仍在继续，并且望不到边际。
         重写E，尝试了4次E，结果都是WA。
         其实，我们并不是面对卡题的情况而慌乱，当时我果断重写了E题，程序结构已经非常清楚了，但是仍然WA。于是，我写了一个测试程序来测试E题，但是还是找不到错误。这确实是我没有遇到过的问题，我不能想象一个能通过1000组随机数据的程序提交之后的结果会是WA。于是我直接把checker放在程序里，提交之后还是错误的。
         尝试了3次C，结果都是WA。
         C题其实就是一群公式的组合，当天zzy做这种琐碎题目的状态还是不错的。不过前几次提交他漏掉了几种情况。
         实现了J的开头，由于信心不足，没有写下去。
         这件事情是很值得一提的，J题其实不是很难，只是当时E题有些苦，所以表现出信心不足。此时比赛时间大概是200分钟，我们一共卡住了2题，并且都已经陷入其中。经验告诉我们，应该开新题了，就是很多队都通过了的H题和I题。
         209分钟，H：经典2-SAT问题。2Y
         H题算法很清楚，只要看到那个more than half就可以了。我仍然延续着除E题之外的好状态，大概前前后后用了10分钟就写完了H。至于为什么WA一次，原因已经不是很重要，当时我们的罚时已经大到不在意几次错误提交了。
         238分钟，I：模拟和数学题。1Y
         I题是挺复杂的模拟题，需要一点数学知识。由于I题比较复杂，写程序过程中我有些着急，但是越着急越影响速度。现在回想起来，写I题是很重要的阶段，如果I再出任何问题，则THU此次总决赛能否获得奖牌都很难说，可以说后果不堪设想。现在还清晰记得zhouyuan每过几分钟就要提醒我一下“别着急，还有很多时间”，他当时的冷静对队伍来说很重要。
         I题在封版前2分钟1Y，也随即拉开了Proxima反攻的序幕，不过确实有些晚了。
         246分钟，C：计算正八面体表面两点最短路径，分16中情况考虑。5Y
         当时我和zhouyuan正在讨论K的算法，当算法基本清楚之后，zzy突然大叫一声Yes通过了重要C题。C题的通过在当时看来很提升士气。于是我们马上做了如下分工，我实现K题的程序；zzy读E的题目描述和代码，由于zzy之前没有看过E题，所以让他重新读题可以有效防止ZSU类似的读错题的情况发生；zhouyuan先与zzy讨论E题，然后出K的数据。
         当时我们通过了7题，还有50分钟时间。在封版时，我们看过board，只有领先的ITMO通过了7题，其实只要过几分钟再刷一下board的话，就可以发现他们通过8题了，但真正致命的是，ITMO是没有过H的8题，也就是说可以认为他们已经通过了9题。
         实现K，由于没有用long long，WA了一次。
         写完K之后，我们其实是抱着试探的心态提交的，当时大概是265分钟，对于这个WA，大家没有表现任何沮丧，可能已经有些麻木了吧。不过当时达成共识的是，K的算法一定没有错，这种决心在最后时刻对一个队伍来说是很重要的。当时我们可以这样认为，也必须有这样的信心。
         270分钟，E：图论问题。7Y
         zzy读我E题的代码过程中，对某一个地方的细节表示质疑，其实他并没有发现错误。不过我脑海突然闪过了一个重要信息，发现我预处理过程中有一个地方少考虑了一种情况，修改只有提交就Yes了。
         E题的算法，其实在第一次提交的时候就已经是基本正确的了。但是至于测试程序还有checker都不能发现错误的原因是，checker和主程序使用了相同的预处理过程，而这个预处理过程写错了，而且重写前后这段处理犯了相同的错误。贯穿全场的悲剧终于结束了，但我们当时已经无力回天了。估计一下，E大概占用了120分钟时间，回想两年前同样失手与E题。
         276分钟，K：字符串问题，可以转化为动态规划和最短路问题。2Y
         K题是一道很不错的算法题，起初我们认为这题是NP-Hard的，于是想写一个BFS，不过由于E题的悲剧就忘记了。后来因祸得福，想到了正确的动态规划方法，不过当时心中还不完全确定它是正确的。不过当时zhouyuan给出了一个需要3^34步的数据，我先没有想long long的范围是否足够就改了后提交了。提交之后，我起身去厕所。5分钟后返回时，他们告知我K题过了，当时还有19分钟。
         在实现复杂的I题的时候(230分钟左右)，我们肯定都没有想到最终能够达到9题之多，而且最后还有19分钟剩余。
         用随机算法尝试J，没有通过
         虽然只有19分钟，我们并没有放弃比赛，无奈之下我使用了随机算法尝试J题，不过奇迹没有发生。J题其实不是很难，算法的关键部分我们都想到了，只是由于前面E和C两题卡得实在太惨了，实在没有时间写了，如果能够多出15分钟应该足够了，或者说，对于世界冠军队来说，35分钟足够通过J题。
         记得比赛结束之后，我跑去问ITMO通过了几题，在听到“NINE”的回答之后，我已经明白自己只能接受两次亚军的命运了。我们由于卡在前期，所以罚时上是没有办法和他们比拼的。今年显示排名的方法很刺激，THU的那条bar很坚挺，不过还是没能笑到最后。
         最终，SPB ITMO同样通过9题，以罚时优势排在第一，我们又一次位居次席。纵观整场比赛，比赛中前期我们由于E题和C题耽误了太多的时间，其它题目总体情况都比较顺利。对于E题的严重失误，我应该承担主要责任，在这里向Proxima和所有关心我们的同学深表歉意。
         赛后碰到复旦的吴永辉老师，他安慰我说，“这也许就是宿命”。其实，无论是赛前还是现在，我都不承认宿命的说法。其实我们完全有能力改变结果，即使在最后一刻。不过，吴永辉老师确实很了解当时我们的心情，如果最终没有做出9题，比如结果是8题排在第4，可能内心中都不会有如此的遗憾。通过9题是ACM总决赛以来之最，至少我们是“历届ACM总决赛过题最多的队伍之一”（一共有3支队伍做到过9题，除了今年的ITMO和THU之外，只有2003年巅峰时期的tomek领军的Warsaw University也通过了9题）。直到现在我们仍然难以接受通过9题而不能夺冠的事实。确实ITMO在中期的状态太好了，引用邬老师赛前的话“夺冠需要一些运气”。
         记得晚餐时碰到了Petr，他见面就直接伸出两个手指，并表示我们的ACM成绩已经完全一样了（Petr曾经在2003年和2005年两次获得ACM总决赛亚军）。我们的总决赛经历惊人得相似，包括两次总决赛都相隔2年，甚至连第一次都被Warsaw University击败都一样。
         2009-ACM/ICPC瑞典总决赛之后，我的ICPC生涯已经彻底结束了。在网络上，许多同学经常问我如下一个问题，其实这个问题都很难有固定的答案，我只是根据自己的经历列举一下自己的体会。
         ACM团队比赛与TopCoder个人赛事相比，对个人能力提出哪些特别的要求？
         首先，我个人认为虽然ACM比赛由3人组成，但是至少应该有1名选手具有很强的个人能力，比较理想情况应该有2名选手能够做到独当一面。
         其次，3名选手对相互之间的代码风格要非常了解。在这一点上与TopCoder中的Challenge能力有些相似，相比之下ACM对此要求还高一些。
         再次，ACM比赛使用在线评测，要求选手能够对于提交的时机有正确的把握。究竟是选择早提交以提高速度，还是谨慎提交以减少罚时，一直是众多队伍需要权衡的重要问题。
         比赛结束后回到清华的几天中，我一直在思考一个问题，Tsinghua（THU）和ITMO等欧洲传统强队最大的差距是什么？
         对此问题，我想直截了当地指出THU问题的所在。THU与ITMO等欧洲传统强队的最大差距是：THU从参加ACM的那一时刻起就没有作夺取世界冠军的准备。
         问题要回到在THU眼中ACM的地位，关于这个问题，大家都有自己不同的看法。我觉得ACM在THU则更像是一个社团活动，或者一种娱乐项目，这一点与SJTU相比简直是天壤之别。我并不认为不同看法之间有任何优劣，只是认为这种对待ACM的态度已经严重影响了我们的成绩，虽然比赛成绩在THU的这种态度下没有任何意义。
         我内心并不反对THU的这种观点。在比赛中，我们充分享受了比赛中的乐趣，同学之间进行了很好的沟通。通过比赛，我得以认识来自全国各地的同学，与他们交流各方面经验。
         但是从另一方面讲，我们没有耕耘，就很难收获世界冠军，虽然世界冠军对THU来说却确实没有什么特别的意义。
         从选手的综合实力上讲，THU与ITMO等欧洲传统强队相比，其实占据了一定的优势，很难有其他学校能够每年录取15名左右的顶尖OI选手。这些OI选手在入学时各方面能力上都优于欧洲强队。但是，他们从入校之后再没有接受过正式的相关知识的学习与训练，大部分选手的最佳状态就是刚刚进入大学的时刻。
         从平时学习和训练上讲，THU与ITMO等欧洲传统强队相比，是截然不同的角度。邬老师在平时沟通中，更像是社团主席，引导我们享受比赛中的乐趣，和选手之间沟通方面都做得很好。但是THU没有像andrewzta，Petr这样的“金牌”教练，有他们的帮助能更好地做到知己知彼，平时THU训练大多都是学生自发组织的，于是THU大多选手好像连“知己”都做不到。亚洲分区比赛中，THU依靠选手深厚的OI功底掩盖了这种平时积淀的差距，而总决赛中却暴露无遗。
         从赛前的训练上讲，THU与ITMO等欧洲传统强队相比，做得远远不够。记得前面提到过：直到赛前，我们的精神状态都没有调整到最好。其实直到出发前3天，我们才勉强能做到每天做一次模拟比赛，不过从社团活动的角度说已经做得很不错了。
         这一年，我很高兴看到OI选手中出现了ahyangyi，yuhch123，Loner等各方面极为出色的新人，他们的加盟，极大增强了清华ACM团队的实力。
         不过，比如明年，即使中国队伍占据主场之利，THU想获得世界冠军可能还需要一些重要的准备。
         首先，从我个人参加ACM已经有4年时间了，与2005年THU的ACM情况相比，这些年来，学校对于ACM的重视程度有了大幅的提高，收益已经体现在了各个方面。但如果想真正登上最高领奖台，还需要思想和态度上有充足的准备，虽然现在看来，这种态度转变在THU是否有意义还值得商榷。
         其次，从赛前训练角度上看，队伍的状态对成绩影响很大。今年虽然THU有机会和Waterloo等名校合练，但是比赛的密度和强度与欧洲各队相比都相差一个档次（其实，今年的校内PK的强度是很高的）。这一点我们应该向SJTU学习。
         最后，在总决赛这种级别的比赛中，“夺冠需要一些运气”，多积攒RP吧，J。同时也预祝所有中国学校总决赛好运。