利用假期空闲之时将这几年GCJ，ACMTopCoder 参加的一些重要比赛作个
回顾。昨天是GCJ2006 的回忆今天时间上更早一些吧，我现在还清晰记得3 年
前我刚刚参加ACM 时参加北京赛区2005 和杭州赛區2005 的情况。
我进入清华大学开始本科学习的时间是2004 年8 月在进入清华大学的第一
年里，由于基础课学习比较紧张再加上计算机系不允许夶一学生自带电脑，我没
有参加2004 年的ACM 比赛不过在大一一年中没有停止这方面的练习，对ACM
大概在2005 年7 月底与同班同学shell（贝小辉）和superzn（张宁）一起
决定组队参加ACM 比赛。对于队名没有太多的想法就随便取了一个字典序靠前
一点的bomber。随后进行的几场训练中我的编程状态一直保歭得很好，训练比
赛的主要方式都是：我主写程序shell 和superzn 负责翻译题目，思考算法和测试
这种组队模式一直沿用到我们后面的所有比赛中。
2005 年底我们报名参加了2005 年的北京赛区和杭州赛区的比赛。顺利通过
了预赛进入了现场决赛记得当时北京赛区预赛的时候，我和superzn 一起在參加
百度之星程序设计大赛shell 依靠一人之力过了6 题，最后以第二名的资格参加
2005 年的北京赛区地点设在隔壁的北京大学由于交通非常方便，我们没有
和大部分选手住在一起不过也没有参加Java-Challenge 和晚上的表演。
练习赛之前说到比赛位置抽签，本身意义不是很大可是邬老师神渏的RP
把两只清华的队伍抽在一起，结果练习赛进行了一半另一只清华的队伍THU1
（队员是：吴景岳，栗师和金凯好像后来队名改成了DreamCatcher，不昰很确
定）被要求换到一个比较远的地方理由是有些学校觉得这样不合理。后来很多赛
区也出现过队伍座位在一起的情况邬老师的RP 果嘫不是盖的。
记得练习赛时和复旦的LemonTree（盛城）一起在场地里闲逛结果果然不到
10 分钟就被要求回座位了。还有当时比赛场地是一个体育馆有些队伍把气球放
飞之后气球就飘在天花板下了，总裁判李文新老师还威胁我们说如果明天正式比
赛把气球放飞，就不算通过相应的題目除非有办法把气球取下来。
然后就是比赛的过程了下面有底纹的文字是我找到的当时留下的比赛总结：
E：快速排序。5 分钟1Y
我想5 汾钟的时间可以争取这几年ACM 国内赛区的最快出题记录了吧。
G：二分答案+最小生成树25 分钟1Y。
这题就是的最优比例生成树问题我们一致认為这题比较简单。不过后来
被李文新老师批评了说法是误导其他的队伍。不过说到最优比例生成树问题
TCO2006 的时候fwj 和tomek 竟然都没有见过这道題目，这题可是源于POI 呀我
想我们认为这道题目简单的主要原因是我们都在冬令营上见过这到题目，如果第一
次看见想出算法可能确实需要一些时间。在这里向被我们影响的队伍的道歉最
终G 提交了200 多次，但是只有8 个队伍AC
C：二分图最大匹配。42 分钟1Y
题目要求计算一张图的朂小覆盖集可能唯一的tricky 是发现图是二分图。
D：遇到了一定的困难发现A 很简单，于是先放一下
D 是一道比较综合的题目设计一些简单的計算几何和字符串处理的知识。
A：简单的几何问题出现了一个低级错误，提交了3 次均为WA
A 是北京赛区最简单的题目，我的程序里犯了一個很低级的错误可能也是经
D：重新写，但是没有考虑一种情况WA 了1 次。
87 分钟复旦的Abuacus 过了4 题占据了Rank1。由于队伍模式的原因我们
在还有佷多简单题目的情况下卡住了长达30 分钟。
A：shell 突然发现了A 程序中的低级错误105 分钟AC，重新夺回Rank1
这是很重要的一步，现在想来如果没有这个發现后果可能不堪设想。
B 是一道明显的2SAT 问题由于题目比较长，我们没有很早发现这道简单题
D：发现了D 的没有考虑的情况，140 分钟AC
式仳赛就做到6-4 的领先，当时心情很激动不过由于缺少经验，也影响了接下来
的发挥其实，现在回想起来这次比赛其实是一个很好的AK 的機会。
F：DP程序比较复杂，WA 了4 次
F 是一道比较复杂的的题目，其实WA 的原因是一个应该用int64 的
地方我们使用了int，这个地方的确很难发现
H：F ┅时无法AC，只好转功HH 就是普通的模拟题。开始没有考虑坦克和
炮弹可能在1/3 秒相遇WA 了1 次。
比赛还有一个小时封板。
H：shell 发现了坦克和炮彈可能在1/3 秒相遇的情况250 分钟左右AC。
对于我们这种组队模式当主写程序的选手状态不好的时候，很容易出现连续
卡题的情况这种情况嘚出现很不利于水平的正常发挥。在北京赛区的比赛中我
们很有幸没有出现连续卡处的情况。
记得当时北京赛区的Judge 的半自动的，就是說如果结果是AC速度就会非
常快，否则由于人的介入不能AC 的提交往往需要等一段时间。我们第2 次提交
H 之后没有得到很快的回复，以为巳经WA 了于是我和superzn 继续测试一些
数据。但此时突然有一个mm 从左边走过来插气球，这个气球也成为了全场唯
一的蓝色气球这个意外之喜朂后成就了第一个分区赛冠军。
F：下面就是痛苦地提交F一直战斗到最后一刻，WA 了14 次留下了北京
在最后时刻我们似乎发现了那个int64 的错误，不过当时思路已经比较混乱了
没能改对。F 的问题也导致没有时间写I当时如果直接重写后者换superzn 来写F，
完全可以在比赛结束前AC
比赛的夶致过程如上所述，那个神奇的气球我现在仍然记忆犹新。最终有4
我只记得辛韬ZSU_Panku 中我记得Savior（陈实）。上述的老朋友之后见面的机
会就佷少了分区比赛也成为了我好需要老同学重要的交流机会了。
我ACRush 的ID 估计就是那时开始使用的吧转眼就已经3 年多了。
比赛前后还记得经瑺与复旦大学的吴永辉老师聊天在那之后的每次比赛我都
现在回想起北京的分区赛，很有幸能够在第一次参加ACM 正式比赛就获得分
区比赛嘚冠军我想是由于现场气氛对许多队伍都有不小的影响吧，当时许多队伍
都卡在几道比较繁琐的题目上了题目的算法性都不是很强。峩大概从那时才刚刚
接触TopCoder如果能够早一些，相信会更适应这样的比赛
2005 年的ACM 杭州赛区比赛在浙江大学举行，杭州赛区的时间就在北京赛區
结束后一周最初选择杭州赛区的原因很飘逸：我自己家在杭州。实际上也差不多
我随队伍（当时THU 派了3 只队伍参加杭州赛区的比赛，除了我们队之外
b142857（侯启明），zhy（周源）ysy（杨 思雨）组队，另外一只由汪汀王俊
和黄源河组成）一同抵达杭州车站之后就马上回家休息了，直到比赛前才赶回在
北京到杭州赛区之间的一周中，我的状态就在 不断下滑在家中完全失去了比赛
的气氛，回到赛场再也找不箌感觉了一场悲剧即将上演。我们先看看比赛过程吧
下面有底纹的文字是我找到的当时留下的比赛 总结：
G：初看很简单，但是调试了30 汾钟没有结果
G 是一道数学问题，其实《具体数学》书上有明确的公式不过我们使用的递
推方法应该也可以得到正确的结果。程序中犯叻一些低级的错误由于实在不在状
态，调试了30 分钟还没有找到错误这里还暴露了一个组队模式的问题，在后来
的组队模式中如果像這样没有想清楚算法的题目队友是一定不允许我去写的。
A：模拟41 分钟AC，当时肯定没有想到这是唯一一道1Y 的题目
A 是一道模拟题，1Y 的时候巳经很晚了排名也很靠后。
C：图论但是由于堆栈逸出RTE 了5 次，浪费了大量的时间
C 的问题关于树中祖先关心的判定，题目很简单实现嘚方法也很容易，就是
通过一遍DFS 来计算但是我们忽视了一个从来没有遇到过的问题：堆栈溢出。
而且堆栈在本地机器上运行过程中，Eclipse 提供了8MB 左右的堆栈所以没有
溢出，但是在提交之后的环境下运行就溢出了而且每次RTE 之后，我们一直在
尝试修改数组的大小一直没有找到根本原因。调试C 的同时我也尝试修改G，
结果G 也错了8 次之多并且始终都是WA。
I：shell 在我郁闷地调试C 和G 中AC 了之前WA 了一次。
I 是动态规划问題WA 一次可能是忽视了一些边界情况。
D：网络流没有想到先贪心进行优化。TLE 了5 次最终没有通过
D 就是计算最小割，我们事先准备了先流嶊进算法不过根据这道题目的模型，
先流推进算法遇到最坏情况：二分图由于当时dinic 还不是很流行，我们TLE 了
E,B：都尝试过但是都出现了鈈明的问题。
在随后的时间里不断调试D 和G，但是始终不能AC之后又尝试E 和B，E
通过分段的方法可以处理B 是数学题目。正常的话E 和B 并不是佷困难的题目
但是当时已经非常混乱，连样例都没有通过
最终我们只过了3 题，排在21 名经历了我参加ACM 以来最惨痛的失败。
这次失败主偠归过与我状态太差基本上什么题目都不能顺利通过。当然题目的选
择也有很大的问题：G 确实不是难题但是由于未知的原因始终不能通过，后来我
把纸上的程序敲在ZJU 上就AC 了至于现场为什么不能AC 我现在还是不能明白。
如果说第一题的选择直接影响了我们的信心那么D 的堆栈溢出则完全打乱了我
们的节奏。对于我们的组队模式卡出2 题已经超出了极限，我们不可能再尝试
Abacus 也来到了杭州他们前期体现了强勁的先期优势，在2 小时就达到了6
题；b142857（侯启明）zhy（周源），ysy（杨思雨）的队伍表现得相当神勇
在最后一小时超越了Abacus，夺得了冠军
杭州赛区的失败至今仍是心中痛苦的回忆，不过这个教训也是对我今后的学
2005 年是我第一年参加ACM-ICPC 的比赛两场ACM 分区赛，我们经历了夺
冠的兴奋也经历了环顾四周等待比赛结束的无奈。2004 年清华没有获得任何分
区赛的冠军2005 年清华打了个漂亮的翻身仗，先后在成都北京和杭州夺嘚冠
军，而且是三支不同的队伍
两个赛区的G 都是有传奇色彩的题目。北京赛区中我们25 分钟1Y 了G，
导致许多队伍跟风失败最终达到了208 提茭8AC 的低通过率。但是杭州赛区
中，G 从比赛一开始就占用了我们大量的时间直到最后都没有通过，估计至少浪
费了两个小时左右真所謂成也在G，败也在G
北京赛区后，POJ 的论坛上传闻说我曾经说过“起身去厕所不许碰键
盘。。”很敬仰那些同学搞笑和扯淡的功底，峩们虽然定下了以我主写程序的
组队模式但是也非常重视配合和每个人在队伍中的重要作用。
当时清华没有组织校内PK 选拔选择了成都賽区的冠军队THU1 参加全球总
决赛，当时总决赛队伍是以参考第二赛区的成绩决定的现在回想起来也是很合理
的。由于最终我们未能得到机會参加全球总决赛接下来几个月我们情绪低落，
bomber 从那时也就宣布解散了吧
2005 年的比赛过程中，我见到了许许多多的老朋友用吴永辉老師的话，
ACM 竞赛可以看作一些老朋友一起进行的一场智力游戏
找不到杭州赛区的排名了，只发现了这个：
谢谢韩家龙同学的热心帮助找箌一个排名的链接是：
利用假期空闲之时，将这几年GCJACM，TopCoder 参加的一些重要比赛作个
今天晚上先回顾Mobile Robot 成立先期的事情吧明天再总结惊心动魄的ACM 上
回忆到2005 年清华没有组织校内PK 选拔，选择了成都赛区的冠军队THU1 参
加全球总决赛bomber 从那时也就宣布解散了。
队伍就已经成立了队伍其怹两名选手是一起参加IOI2004 的geworm(鬲融)和
次合作的时候使用的帐号，如果回到2004 年的PKU 月赛也许可以看到thmr3191
Robot 的缩写。当然我们觉得Mobile Robot 读起来也比较容易上ロ
我们队伍的主要模式都是：
(1) geworm 全程负责读题，思考算法和出数据；
(2) wd.h 和我在比赛前2 个小时一起攻简单的题目；
(3) 2 小时后wd.h 就开始死磕难题我主写程序一直到3 个半小时左右，结
合wd.h 对难题的把握大家开始合攻难题。
这种拖后中卫的打法对于NEERC 的题目难度非常合适，两场比赛我们嘟做
到了AK（全过11 题）这种组队模式也一直沿用至总决赛。当时wd.h 的状态很
好对于NEERC 的题目难度，我觉得世界上很难有队伍能够有信心做到AK
队伍成立初期的顺利使我们更有信心，我们利用署假时间进行了一些必要的训
练以迎接2006 年下半年的ACM 分区比赛
北京赛区预赛——网络赛賽网络：
2006 下半年有3 个国内赛区，包括北京上海和西安，其中北京赛区最先举
行2006 年北京赛区的地点设在了清华大学，这也是我唯一一次參与组织ACM 分
10 月 中旬举行了北京赛区网络预赛网络预赛的参与者是所有报名参加北京
赛区的队伍，以决定哪些队伍拥有参加现场比赛的资格那段时间，我们队伍主要
精力放在了 准备比赛上我们都没有参与网络预赛的命题和测试平台工作。由于
清华距离上次承办分区比赛巳经相隔很多时间直接导致网络比赛过程中出现了严
重的网络问 题，在这里作为清华ACM 队的一员向受到影响的队伍道歉
不 过，我也是作為“局外人”来了解这次网络阻塞的因为我确实没有参加
任何与网络赛有关的活动。现在回想起来我认为平台的稳定性是一个不可推卸的
原因，但 是主要应该归咎于题目描述和样例的设计当然还有测试数据的错误。
设想这样一种情况如果一个比赛过程中，从某一时刻起突然增加1000 个提交
需要rejudge，然后所有队伍还都在这一时刻起尝试提交我想现有的大部分OJ 都
很难在1 小时之内平息这些提交吧。再举一个哽夸张的例子如果OJ 准备的测试
机器的测试速度已经完全跟不上提交的速度，那么卡住是不可避免的我们通过网
络预赛的教训总结出一些网络预赛题目的重要经验：
(1) 对于容易上手的题目，测试样例一定要足够强
(2) 对于简单的题目，必须仔细确保测试数据是正确的
(3) 题目描述必须没有任何歧义，避免选手通过提交来不断尝试各种理解
如果题目能够很有效控制提交数目，对于测试系统的要求其实不是很高唎
如复活赛和现场决赛的时候，测试系统会大部分时间处在空闲阶段反之，如果提
交处在上述病态的情况下只有非常专业的测试系统財能胜任这样的挑战，当然不
总之对于网络问题我作为清华ACM 队的一员深表歉意，如果还有下一次的
机会我们一定努力做得更好。
如果說网络预赛过程中网络出了一些问题，那么决赛则是结果更出乎我
们的意料之外。在北京赛区现场赛之前几天我们3 支队伍进行了验題赛，比赛
虽然不正式但是过程仍然很激烈。
先列一下决赛的9 道题目吧：
现场赛只有BEHI 这4 道题目有队伍成功通过可是在验题赛中我们队伍的进
程完全不是这样，下面是我们的做题情况：
22 分钟 A 题数学方法，1Y
首先我们3 支队伍在30 分钟之内都1Y 了A 题。A 题是一道中等难度的数学
题可能A 题需要明确高次等差数列的求和公式，而且通过枚举来代替一些假设
可以大大简化问题现场比赛时有些队伍做了不正确的假设导致始终WA。
记得当时zhuzeyuan 使用了一个奇怪的贪心方法后来被OpenGL 找到一个反
例，这个测试用例被添加到正式比赛的测试数据之中这个反例也成为叻现场赛中
使得许多提交WA 的重要数据之一。
E 是2006 北京赛区最简单的题目只需要直接的贪心法就可以解决。
52 分钟H 题深度优先搜索，1Y
H 是一道搜索题题目时限不是很紧，不需要太多的优化就可以通过
75 分钟I 题，标准的博弈SG 问题1Y
I 是标准的博弈问题，通过计算SG 就可以得到结果這题其实有一个阴险的
地方，就是当某位置石子为大于0 的偶数时也需要考虑以保证结果的字典序最
小，好在我们及时避开了这个陷阱現场很多队伍调入这个陷阱中，耽误了一些时
129 分钟B 题最短路径问题，3Y
B 是一张平面图的最大流问题由于图形比较有特点，所以可以建图來计算最
小割但是这张图有106 个点，2*106 条边最短路径需要用堆来辅助实现，首先
由于数组开小了RTE 了一次然后由于用map 实现TLE 了一次。这题浪費了许多
G 题实现和调试了30 分钟，超时
G 是2006 北京赛区最困难的题目之一题目描述很简单，判断一张图是否为
co-graph我们算法的复杂度是O(n*m/32)的，不過由于数据个数比较多程序运
C 题，贪心法实现50 分钟WA
C 题是计算平面图曼哈顿最小生成树，直接计算是O(n2)的但是题目中n 接
近100000。我使用了一個贪心算法其实和标准算法差距不大，不过还是导致
WA其实提前写C 不是很合理的选择，当时没有注意到DC 和G 难度相差无几。
F 题是很变态嘚构造问题这题完全是wd.h 做的，我至今还不是很清楚算法
250 分钟D 题，计算几何2Y
D 题是一道比较复杂的计算几何，当判断一条直线是否穿过┅个多边形的时候
忘记考虑了一种情况WA 了1 次。现场许多队伍其实都只忘记考虑了这一种情况
但是可惜没有队伍该正确。
这场比赛最终峩们队伍以7 题结束另外两队也都通过了7 题。我们因此也
没有修改题目难度随后让大家没有想到的是：一场极低通过率的比赛即将开始叻。
现场比赛中我负责在某一个房间为参赛选手送打印资料，比赛60 分钟左右
由于技术问题到Judge 室处理一些问题经过5 个小时的比赛，最终Φ科大
Student 队通过4 题获得冠军厦门大学btALT 通过3 题获得亚军，北京大学
回顾比赛现场过程首先让我们出乎意料的是E，E 是2006 北京赛区中最简
单的题目贪心法的方法参加比赛的同学都想到了，可是有一个小小的细节对于
实数比较大小时，需要加入一个微小量eps 来控制精度E 题没有加eps 嘚提交占
到总提交的50%以上，我们称之为“经典提交”这个小tricky 不慎导致很多队伍
迟迟不能通过第一题，对许多队伍的状态有不小的影响
其次是A，A 题收到了很多队伍的提交但是最终都没有队伍通过A。原因是
大家做了一些不保证正确的假设当时我们都通过枚举的方法避免叻这些假设。
另外有一些队伍提早接触了F 和G，并深深地陷入其中中科大早在240 分
钟就通过了第4 题，可是之后他们在G 上花费了不少精力峩们甚至想跑到他们
那里告诉他们G 是最难的。
记得180 分钟到240 分钟我们只接收到了不超过10 次提交，每次大家听到
提交的声音所有Judge 一起点鼠標抢测试权。后来在TCCC2006 上和Ying 说起
此事，据他说和2004 年的广州赛区有许多相似之处
赛。并再次对网络赛给大家带来的不便道歉后来清华举荇了名为复活赛的比赛，
我想复活赛应该就是从那时开始出现的吧
当年清华一共有6 支队伍，但是只参加两个赛区的比赛造成每个赛区の前
都要进行小规模PK，最终只有4 支队伍有机会参加ACM 分区赛Mobile Robot 建
立之初比较顺利，获得了参加两个赛区比赛的机会迎接Mobile Robot 的将是上
我们3 人能夠走在一起，要感谢吴文虎老师的支持组队初期虽然没有经历
大战，但是那些快乐的时光至今都很难忘怀
利用假期空闲之时，将这几姩GCJACM，TopCoder 参加的一些重要比赛作
收昨天晚上回顾了Mobile Robot 成立先期的事情吧，今天先发惊心动魄的ACM
回忆到当年清华一共有6 支队伍，但是只参加兩个赛区的比赛造成每个赛
区之前都要进行小规模PK，最终只有4 支队伍有机会参加ACM 分区赛Mobile
Robot 建立之初比较顺利，获得了参加两个赛区比赛嘚机会迎接Mobile Robot 的
将是上海和西安赛区的挑战。
比赛前：空前的豪华阵容
记得清华大学出发上海赛区的时间是10 月20 日晚上至于为什么能记得洳此
精确，是因为在那之前我经历了真正意义上的“赶火车”10 月18 日TCCC2006
在圣地亚哥落下帷幕，19 日从旧金山机场起飞会北京飞机着陆时间是20 ㄖ下午
2 点半，进海关之后已经快4 点了我立即乘坐机场大巴直奔火车站与大部队会合，
之间都没有时间回寝室
来到中亚饭店报道拿到参賽队伍名单的时候，就赫然发现上海2006 的参赛队
伍实力达到了几年来一个不可逾越的巅峰上海交大的1234 队都出现在了名单中，
还有浙大和北夶的Final 队都来了这些还不够，芜湖一中的Loner(周冬)上海微
软ATC 的lympanda 也参加比赛。上海交大一直是这几年来清华国内最强劲的对手
如今交大又占據主场优势，实力深不可测上海微软ATC 虽然是旅游队，但是
lympanda 凭借在TopCoder 上的表现没有人敢轻视这位无冕之王的实力。
对于上海赛区清华也派出了华丽的阵容，参赛的有3 支队伍除了Mobile
大家一起围圆桌吃饭，朱晨光突然和旁边的王俊说好像就我们两个没有参加过
IOI，然后另一边林希德补了一句就我们三个不是金牌。
我第一次有机会敬仰候启明的时候是自己第一次参加NOI——NOI2002 天津，
候启明以满分的成绩获得冠军当时的亚军就是林希德。之后的冬令营我以非正
式营员参加测试神奇得获得第三名，但更重要的是冬令营测试的冠亚军就是候启明
和林希德之后我再没有和两位前辈在OI 上交过手。时光飞逝我代表bomber
队参加2005 年的杭州赛区，被候启明领军的Legendary Team打得一败涂地随后
得亚军的候啟明同住在总统套房。其实在上海赛区之前我没有在正式比赛中战胜过
然是Target（你可是早点在今年Final 之前把Target 拿回来呀几次涨停就可以
了），實力也不在前二人之下
面对知根知底的Shangri-La，大家都知道一场大战在即从实力上分析，我觉
得Mobile Robot 略弱不过赛前我们都没有信心一定能够在仳赛中占据优势。而
且我们心里深知上海赛区的结果将很有可能直接决定清华大学当年的总决赛队伍。
面对这种残酷的现实我们都无鈳奈何，有时一些有实力进军总决赛的队伍在清华
都没有机会参加分区比赛
个人的经验看来，我认为在势均力敌的时候最重要一点是奣白自己的优势和
劣势所在，要用自己最强的方面来对抗对手避免暴露出自己的劣势。我想在这一
点上Shangri-La 可能没有我们做得好Shangri-La 的优势是彡人的总体实力很强，
他们完全可以采用三大高手的组队模式；我们组队时间长配合默契，而且当时自
己刚刚从TCCC2006 以100%正确率回国保持了良好的状态。从单人比赛上讲
当时我的状态即使有Petr 和Tomek 在场，我都并不认为自己一定会有明显的劣势
比赛场地是上海大学的一个大体育館，现场气氛很热烈想到我们用4 个机房
办的北京赛区的现场比赛，不由地觉得有些寒酸
在场外碰到了lympanda，他向我了解刚结束的TCCC2006 的情况峩于是给
他描述了一下几道现场比赛过程中1000 分的题目，结果全部都被panda 秒杀了
无限敬仰呀！同时也第一次见到了周冬。
提一件飘逸事情記得当时练习赛有3 题，封版时没有队伍通过B 题但是其
实在封版后我们通过了这题，我们应该是当时唯一在练习赛中AK 的队伍记得之
后好潒还和中山大学的郭老师交流过这题。不过至于B 为什么能够AC：B 题是一
道需要SPJ 的题目可是练习赛的时候没有SPJ，而我又坚信自己的程序是正確的
于是我不断提交。可能是由于Judge 不耐烦了才用Yes 的方法让我们停止。
比赛之前的晚上我们都休息得很好第二天早上以充足的精力迎接史诗般的上
比赛过程：400 米赛跑
我中学是很喜欢参加400 米比赛，400 米比赛从起跑姿势角度应该认为是短跑
但是400 米已经远远超过了冲刺极限。所以400 米跑中要求我们从发令枪响起的
时候就加速启动，直到拼尽全力为止
我们回顾一下比赛的过程吧，上海赛区比赛之后我们写下叻详细的比赛过程：
按照一贯的方法，鬲融从A 开始读胡伟栋从J 开始读，我准备编程的环境
然后从中间选择题目读。鬲融读完A 后发现A 昰一道简单题。于是选择先写A
A：给定ACM网上预选赛的比赛晋级规则求每所学校的晋级队伍数。
简单模拟题时间复杂度O(N)。本题题目有一个疑问：一个学校出线的队伍
数目可能比该学校参加预选赛的队伍数目还多但是题目描述和样例表明不需要考
ACM 比赛的第一题的选择对比赛嘚进程影响很大，当没有优先选择比赛中最
简单 的题目时更需要保持冷静。
在我写A 的过程中鬲融看了B 和C，发现C 也非常简单于是马上莋C。
C：将一棵节点带权的树划分成两半使两半的权值和的差最小。
枚举或者树的遍历时间复杂度O(N)。去年有一个深刻的教训：当遍历树嘚
时候很容易造成堆栈溢出(杭州赛区留下的疙瘩)。对于本题的范围保险起见没
有使用DFS，而是使用BFS使用BFS 略微增加了编程量，但是可以茬一定程度
鬲融发现D 是一道经典的统计题在不到3 分钟的讨论后，我们得出了可行的
算法于是下面写了D。在写D 的时候鬲融和胡伟栋把題看完了，经过讨论
决定胡伟栋开始想一道数学题I，而鬲融继续看题义不是很清楚的G 和J 两题
D：给出平面里的一系列点，要找一个矩形使矩形边上的点最多。
离散化后先判断一条直线的情况。枚举两条横边然后枚举竖边，一旦一条
右边的边比左边的边好左边的边僦不会再有作用。因此枚举竖边的过程很容易
这题其实存在O(N2logN)的算法，我想出题人也应该没有在第一时间想到吧
做出D 后写了B，原因是B 的算法相对简单但是意想不到的是：B 的样例不
合法，而且Clarification 的速度非常慢于是只好先把B 放在一边。这个过程浪费
随后看到team109(Shangri-La)过了一道红色气浗感觉是G，于是鬲融给我讲
了G但是发现G 实在不像算法简单或程序简单的题目。
此时胡伟栋推出了I 的一个很简明的公式。而且我们发現I 的气球也是红色
的刚才看G 很可能是被误导的。于是写了I
写I 的过程中，由于鬲融看的题基本已经被做完了胡伟栋给鬲融讲了H 的题
意，鬲融想出了一个可行的做法不过由于还有更简单的题并没有马上做。
I：求杨晖三角形第N+1 行不能被质数整除的数的个数
可以找出规律，然后写出公式时间复杂度O(logN)。我在并不知题目意思的
情况下写过了I依靠胡伟栋的公式，我们度过了此次比赛第一段艰难的时期
从过D 題到过I 题，大概有40 分钟的时间这段时间我们主要的失误有：
(1) B 的样例不合法，这其实不是我们的错误
(2) 受气球颜色的误导，过早思考一道佷难的题目
(3) 后来听朱泽园的建议：由于一个人的问题导致卡住，应该一个人解决不
应该让全队都陷入混乱中。
我认为我们直接选择写叧外一道题目主要有两个原因：一是B 卡住的原因比较
特殊不是我们花时间就能克服的；二是I 的算法比较清楚，非常稳定
B：给出16 个数，將他们排成十字架形使力矩平衡。求本质不同的方案数
十字架一共有4 个“臂”。首先找出一个“臂”的所有情况然后将等值的无
重複的合并成两个相对的“臂”。然后从16 个数中选出8 个将他们作为一组，
另外8 个作为另一组这种方案的总数为前8 个成对的方案数乘后8 个荿对的方案
数。最后把方案数求和除4
本题属于搜索题，而且时限特别紧由于搜索问题的优化空间往往很大，而且
又是多组数据所以佷容易造成TLE。在调对样例后TLE 了一次改进了算法后
由于开小数组RE 了一次，终于在第三次提交通过了B 题
记得高中时一次在网上做题(只记得昰xreborner 出的题目)的时候，比赛一开始
就写一道时限很紧的题目估计开始程序的正确性是没有问题的，就是效率比较低；
但是在不断优化的過程中改错了程序，导致1 个小时以后当程序不TLE 了以后
程序变成了WA。这样使得信心完全崩溃
听了很多同学讨论之后，发现不少队伍就完铨卡在了B 题上以后对这种题目
只能倍加小心，现在我们还没有什么特别好的方法而且，B 题的样例只具有测试
性不具有调试性，编程時必须特别仔细才行
这时大概才1 个多小时，我们看似顺利地通过了5 题；但是现场的情况并没有
任何优势可言Shangri-La 在几分钟后通过第5 题，两個队伍的罚时只相差1 分钟
随后我们到达了第二段艰难的时期，主要原因是鬲融把F 的题目看漏了一个条
件与胡伟栋讨论后误以为这个题仳较容易，很快这题出现Run-time Error 好在重
读题后发现错误并及时放弃没有再浪费时间去把Run-time Error 调成WA。如果
当时死做此题则后果不堪设想
在鬲融和胡偉栋分别读F 的程序以及题目的时候，由于现在剩下的题目都比较
复杂我们选择了一道相对清楚的题目H 继续做。
H：对一个集合进行两种操莋：插入一个数和询问MOD Y 最小的数中最后一
由于数字的范围是[1..500000]先选择一个合适的M。当Y<=M时通过插入
时直接保存来处理，当Y>M 时直接枚举用並查集求一个元素的后续。这样每一
但是开始选择M为1000，并没有充分估计复杂度的平衡性开始我们认为
并查集的常数较大，但是后来感覺到并查集的常数相对小一些于是把M选为
500 就过了。后来在同出题人交流的时候被告之M取在400-800 的范围内都可以。
第二段艰难的时期的原因鈳能不仅仅是题目看漏也由于题目难度已经增加。
好在当时特别是当H 的程序TLE 之后我们都比较冷静，相信自己H 题的算法是
正确的算法呮是参数的选择不够合理。这种考验在平时一般是很少遇到的经受
这次考验之后，再遇到类似的问题我们应该能够更冷静一些。
过了H の后鬲融已经再次确认了J 的题意，随着气球的指引我们决定攻克
本次比赛最大的“纸老虎”：J，而做J 的过程中胡伟栋一直在想G已经夶致得
J：给出一些数的大小限制的关系，求更精确的关系后者判断为矛盾
转换成图的模型，不断迭带调整直到不能调整为止。当然这題由于大小限制
关系中既有’<=’还有’<’所以需要判断XI<XI 是不合法的。时间复杂度O(N
J 题的数据输入输出比较复杂但是题目本身很简单。这題对编程能力提出了很高
通过J 题之后看了一下board，当时Shangri-La 只有5 题不过在我们还没
有反应过来的时候Shangri-La 就也同样7 题了，罚时上我们领先4 次提交
在比赛的前200 分钟，我延续了TCCC2006 的良好状态我们配合默契，在面
对BHJ 这样琐碎的题目时队友会提前把需要注意的细节总结在纸上，整个 过程
都保持得很平滑另外，鬲融和胡伟栋在我做每一题时都准备了很合适的测试数据
大大减小了我测试的时间并很有效地提高了提交正確率。由于剩下的题目难 度明
显高出一个档次在通过7 题时的罚时领先是最后获得比赛胜利的重要砝码。
现在剩下的只有EF，G 三道没有队通过的题目了其实最终也没有队伍通
过。我们曾经读错过F因此这次分别尝试了E 和G，但是都失败了这里我们曾
经讨论过先做E 还是先做G，当时面临的选择是：E 的复杂度估计较高不知优化
后能否通过，而G 的算法性更强胡伟栋仍然没能完全清楚如何解决，实现的复
杂度高於E我们这次带有赌博性的选择了E，并没有仔细考虑如果E 的时间要求
过于严格会出现什么问题（可能与B 的相对轻松通过有一定关系）在此后的比
赛中我们应该注意周全考虑，尽量选择题意清楚并且复杂度容易估计的题目
E：带限制的有向图的第K 短路。
本题其实有标准的A*算法我们也使用了这个算法。但由于复杂度过高我
们的程序一直TLE。据Judge 说这题对时间的要求非常严格
G：在一个森林的若干点布置仪器，儀器有作用范围D仪器之间的距离需要
大于等于D，求最大的覆盖长度和最小的权
本题可以使用二次方状态的动态规划，类似CTSC2004 的一题我囷胡伟栋讨
论后成功想出了正确的方法，并且在最后时刻写出了程序而鬲融和胡伟栋则出了
一些测试数据，将数据调过后时间已经很紧張了首先由于忘记优化floyd 超时了
几次。在优化了floyd 算法之后还是没有考虑到图不连通的情况，未能在比赛结
F：给出一些公理假设和定理の间的关系，依次尝试推出尽可能多的定理。
在同等情况下要求使用的假设最少
本题可以用最小费用最大流解决，但是比较容易实现嘚网络流算法都很难在时
现在看来EFG 三题中的E 没有比赛中想像得那么难，当时比赛中受到巨大压
力的影响没能攻破此题不过FG 题即使出现茬CTSC 难度的比赛上也非常合适。
比赛结束时我们与Shangri-La 同为7 题上海交大一队最终也通过了7 题，我
们依靠罚时的微弱优势险胜经过惊天地泣鬼鉮的300 分钟，我们终于获得了梦寐
以求的2006 上海赛区冠军Mobile Robot 凭借着上海赛区的夺冠，已经可以认为
获得了进军2007 东京世界总决赛的入场券
比赛結束后见到了很多复旦的老朋友和吴永辉老师，吴老师还是和以前一样
玩笑开个不停。那些复旦的老朋友赛前由于是参与出题我们一矗没有看到，颁奖
仪式之前我们终于有机会在后场一起聊天。不过聊天这些时间中我和b142857
错过了郭老师在颁奖仪式前进行的“点名”（當时郭老师要求我们上去讲解题目），
首先向Shangri-La 致敬即使在最后一刻，相信大家都还仍然有机会棋逢对
手也是我ACM生涯中的一大幸事。当兩支队伍都通过7 题的时候排在第3 名的
队伍才刚刚5 题。也就是说我们两支队伍其实只用了2/3 的比赛时间就锁定了上
上海交大一队最终也通過了7 题，比赛开始时我们就注意到了交大开场时非常
不顺利不过顽强的交大一队稳扎稳打，在最后一小时也成功通过了第7 题在这
里向茭大致敬，开场的种种不利不亚于我在杭州2005 时的起跑你们能够沉着应
战，破釜沉舟的精神一直值得我们学习当时交大一队中有一位来洎辽宁的选手辛
韬，记得NOI2003 之前我们有数次交手都以我失败告终后来经常在许多网上比
赛中切磋，2005 年ACM 北京赛区也有你熟悉的身影在清华早有耳闻你在交大的
优异成绩，祝福你今后越来越好
这次比赛的命题工作是由复旦大学担任的，复旦大学的命题特点与东欧的命题
风格佷接近题目的算法性偏强，题目对程序运行速度要求普遍高
按照panda 的说法，上海微软ATC 队由于一些配合的失误最终只通过5 题，
不过也是湔10 的队伍之一另外，芜湖一中队也顺利通过5 题排进前十GotoFly
通过第3 题的时候还排在第3，不过后来卡死在J 上了有些可惜。
后来分配总决賽名额的时候，上海赛区得到了10 个总决赛名额这个数字
相信也是这些年来的之最吧。
这是一场值得纪念的比赛参加2006 上海赛区的强队实仂远高于几年内的各
大赛区，能够站立在上海赛区的最高领奖台是Mobile Robot 获得的最高荣誉之一
经历了上海赛区大战的洗礼，接下来的西安赛区絀场的则是更成熟的Mobile Robot
利用假期空闲之时，将这几年GCJACM，TopCoder 参加的一些重要比赛作
艰苦的ACM2006 上海赛区结束之后我们原本以为清华会选择另外3 支队伍
参加西安赛区的比赛。况且大三的课程的实验任务很重，我们也就停止了计划的
定期训练大概在25 天之后，12 月20 日左右突然收到邬咾师的通知准备出发
参加ACM 西安赛区比赛。我们的2006 西安之旅也就是在这比较仓促的准备中开
西安赛区之前我们没有定下明确的目标，比賽过程中处处都采用了追求稳健
的方法当时也是为了避免一年前的杭州悲剧重演。
西安的比赛没有太多兴奋的AC没有惊心动魄的场面，所有过程都在类似旅
游的气氛中结束了作为Mobile Robot 的最后一战，这里也作一个简要的回顾吧
由于这次题目又是Srbga（刘汝佳）命题的，我最后也順便列举一下我总结的他命
2006 年清华同样派出了3 支队伍参加西安赛区除了Mobile Robot（我，
和liuhe(刘贺)如果你第一眼看见这个词就知道是什么意思，我楿信您一定准备过
2006 年冬天是我第一次来到西安刚下火车就深深感受到了西安的古城气息。
到达宾馆之后我们做得第一件事情就是玩，茚象很深的是钟楼鼓楼还有大雁塔。
我们做的最主要的事情可以用GotoFLY 的4 个大写字母GFLY 来表示就是“公
比赛之前的晚上，我们认真讨论了比賽中采用的策略参加西安赛区没有太多
传统强队，我们一致觉得应该优先采用比较稳健的策略赛后有比较简短的总结：
按照一贯的方法，鬲融从A 开始读胡伟栋从J 开始读，我准备编程的环境
然后从中间选择题目读。与上海赛区相比比较顺利的是我一下就看到了一道仳较
简单的题目B，于是我马上写了B 题
B：使用火柴棒拼接数字，给定n,m求使用不超过n 根火柴棒拼成的m 的倍
本题主要的思想是动态规划，方程很容易得出时间复杂度O(nm*10)。但是
(1)如何得到最大的数字标准的方法是使用BFS，搜索的过程中必须非常注意
搜索的顺序但是这样实现很容噫出错。我注意到了n<=100 的条件因此结果不
会超过50 位，于是我使用3 个int64 来保存结果这样既实现简单又不容易错。虽
然程序常数比较大但是鈈至于导致超时。
(2)不能不使用火柴棒而数字0 也需要火柴棒来拼成。例如n=5m=97 的结
ACM 比赛的第一题的选择对比赛的进程影响很大，此次比赛很荿功地使用了
E：标准的课堂睡觉问题求最早所有人不睡觉的时间。
简单的模拟题而且时限很宽松。
E 其实是最简单题目但是由于我的低级错误，不仅得到了一次罚时而且浪
费了宝贵的时间。好在当时比较冷静很快改正了错误。
D：对于一个不超过100*100=10000 的表达式可以在其Φ加入*来表示任何
字符，如果一个表达式只能和唯一的等式对应则称为A 类表达式。给定一个表
达式B要求通过改变最少的字符使它变成A 類表达式。
本题使用了一次搜索再检索的方法可以有效控制程序的速度。估计时限问题
后选择先提交节省了不少时间
J：给定一个4*4 的网格的边框图形，问是否可以通过在4*4 的网格上放6 个
2*2 的正方形框得到
H：给定一组旋转后的乐谱及初始音符及结束音符，求原始的音符序列
開始胡伟栋没有看到旋转的角度是整数的条件，于是推出了可以解决实数角度
的数学公式但是由于公式需要考虑的情况比较复杂，幸运嘚是我们使用了枚举角
写了读入部分之后看到Panacea 过了H 题。鬲融重新读了题目发现了角度是整
数的条件，于是稍微修改就得到了正确的程序
本题需要判断的条件很多，需要考虑得很仔细：
(1) 先把坐标按照X排序
(2) 通过初始音符及结束音符得到sd，判断sd 是否在1 到5 之间
(3) 判断相邻两個字符的距离是否在sd 到5sd 之间。
(4) 判断每个点的坐标是否可以对应一个音符
F：求3 维空间的Voronoi 图，输出每个Voronoi 块体积占的比例
胡伟栋提出了本题嘚正确算法：分割立方体。如果一个立方体的8 个顶点都到
一个点最近那么这个矩形内的所有点都到这个点最近，否则就分割这个立方体
直到立方体的体积少到一定程度为止。
开始程序的精度不够后来胡伟栋提出了一个启发式的分割立方体的方法，思
想就是使得两个立方体的分割面以尽量大的概率穿过Vorinoi 平面程序的效果很
好，而且那时时限也已经放宽于是顺利通过了F 题。其实本题蒙特卡罗法也可
以过我们也想到了这个方法，但是由于随机过程写的效果有问题导致精度不够。
通过F 题的时间是270 分钟封版时除了Panacea 通过4 题，其他队伍最多呮
有3 题当时Panacea 正好坐在我们背后，很可惜他们卡在了D 和G 上最终也
只有4 题。最后半小时我们也没有尝试H 或者A因为其他队伍很难在最后一尛
时通过4 题。我们就简单尝试了几次C 就默默地等待着西安赛区比赛的结束
最终我们通过6 题排名第一，由于已经获得了上海赛区的冠军鈈参加ICPC
的排名，不过仍然获得了Solaris 杯
西安的ICPC 冠军是北京大学的T2（rainer，dzx 和cici）后来他们依靠西安
的夺冠成绩进入了2007 年的全球总决赛。T2 在最后一尛时表现极其神勇顺利通
过2 题一举超过了GotoFly 和Panacea，而且最后几分钟还很有希望通过H赛后
和rainer 讨论之后发现算法相差无几，可能就是一些小细節缺陷吧 年
度的ACM 比赛，从上海到西安还有东京的总决赛，Mobile Robot 每次比赛都能
看到了T2 熟悉的身影我们在封版之后常常由于压力较大很难攻破题目，他们在
封版之后的冷静心态非常值得我们的学习
题依靠罚时优势排在第四。两队都欠缺一些运气很可惜。另外印象很深的是坐
在对面的朝鲜队通过了4 题在ICPC 中排名第2，如果西安能够多一个名额的话
他们就能够出现在总决赛赛场了。
西安赛区是Srbga（刘汝佳）出的題目从高中时期就开始做了Srbga 出的题
目，西安赛区的题目又一次体现出了刘汝佳命题的许多重要特色：
(1) 如果Srbga 大哥出是一套题目那么你会奣显觉得题目拿在手上明显重一
些。Srbga 大哥出题很重视题目描述或者故事的完整性他很少使用一些僵
硬的题目模型和描述。有时读着他出嘚题目更像是在读小说欣赏故事。
当然由于Srbga 大哥出的题目描述完整，刚拿到题目的时候会感觉很难
上手我们很容易发现没有一道题目容易上手。用数据表达比赛开始时
(2) Srbga 大哥出的题目和世界总决赛的题目风格近似，题目多半对编程能力
提出很高的要求相比之下对算法的要求不是非常高，考察的都是比较基
本的算法如果用一个字形容就是：野。
(3) Srbga 大哥出的题目对算法的考察范围非常广虽然对于某特殊的算法要
求不高。有时还需要很强的组合算法能力
(4) Srbga 大哥出的题目中很注意数据的设计，例如C 题中特别生成了极端的
情况J 则使用了接菦20000 组数据。一般情况下不经过精心设计的随机
Mobile Robot 来说是丰收的一年，我们圆梦了上海和西安的双冠军在随后的冬天，
我们加紧训练准备東京的总决赛
利用假期空闲之时，将这几年GCJACM，TopCoder 参加的一些重要比赛作个
世界在校学生的程序设计大赛2006 年的TCCC 在圣地亚哥举行。从北京箌旧金山
的飞行只需要11 个小时左右所以不至于那么疲劳。路上一切都很顺利很感谢
OpenGL 的提醒，对于超过8 个小时飞行自带拖鞋和枕头对我來说还是很重要的
TCCC2006 使用的标准的TopCoder 现场比赛形式，比赛有48 名选手参加首
先48 名选手被分为16 个人一组，每组分别进行半决赛前2 名直接晋级決赛，3-
决赛由8 个选手参加TopCoder 现场比赛中很重要的一个创新是：每名比赛选手
在观众席前都有一个同步的显示器，这样观众可以看到选手任哬时刻做的事情极
下这两场激烈的比赛吧。
至于3 个房间的分配TopCoder 按照注册截止时选手的Rating 分布蛇形分配。
但是TCCC2006 的房间实力分布极不平衡峩与上届冠军tomek，著名选手reid
1，赛前Room 1 成为公认的死亡之组
在圣地亚哥，我和师兄Macsy（张一飞）同一个房间很感谢师兄的关心，我
那几天休息的都很好要知道如果同房的人有10 小时左右的时差的话，一人必须
很小心才能保证不影响另一人的休息
Room 1 在我抵达美国的第二天早上进荇，选手允许提前30 分钟准备一些必要
代码不过现在大家都比较喜欢学习Petr 那样一行代码都不打。下面就是比赛的
250 分题目是：给定n(n<=50)个整数AI 和┅个阈值d计算n 个整数所有排列
PI 中满足|API-API+1|<=d 的排列中，所有不同可能AP1 的个数这题最标准的方法是
动态规划，基本思想是把n 个整数排序之后計算两条相邻元素不超过d 的序列。
我使用了一种更精巧的算法把n 个整数排序之后，对于AI如果AI 可能作为排
列的第一个元素，那么AI 必定在某一个方向（大小）连续而在另一个方向每间隔
两个元素相连这个算法比较容易实现，但是正确性证明比较难甚至让人第一感
觉是错嘚。我写完程序测试了所有样例都正确就提交了243 分。提交之后我又测
试了许多数据并在纸上尝试证明正确性。
赛后我看了网络上的討论记录。在我提交250 分题之后立刻遭到了misof
的怀疑，他认为我的算法有问题据Macsy 学长的回忆，OpenGL 在我屏幕前看我
写完程序也认为我的算法昰错的，不过后来他们讨论之后发现没有反例
而是250-600-900。现在看来对于250 比较顺利的情况，应该先做500若250
不顺利或者想出奇制胜的话，可以先开1000 分当时没有什么经验，我认为900
比600 应该简单一些于是就打开了900。
900 分题目是：给定一张n(n<=10)个点的带权有向完全图（也就是n2 个实数）
和一個衰减系数p求一条经过d(d<=10)条边路径（不需要保证简单路径），要求
这条路径的指数衰减长度（指数衰减是指第i 段的长度乘以pi-1 然后求和）最接近
1000这题如果使用穷举法，就需要1010 左右的计算量在TopCoder 的测试机上
也不能通过，由于路径长度很容易超过1000所以很难找到多项式时间的动態规
划。我马上有了一个想法——双向搜索对于长度为d 的路径，其实可以看作从
某一个点p 出发的一条反向的长度[d/2]的路径和一条正向的d-[d/2]的蕗径对于
固定的节点v 来说，这种两个方向的路径都不超过n[d/2]这样只要枚举一个方向
的路径然后二分查找另一个方向即可。复杂度是O(dn2+[d/2])
现場比赛调试环境不是很好，我花了不少时间调试以发现程序中的错误提
交之后690 多分，还不到700不过对于900 分的题目在那种压力下还可以接受。
提交之后我花了15 分钟左右测试没有发现错误。于是就准备做600 了
600 分题目是：一道经典的数学题，给定一些盘子叠放的规则计算顶層盘子
的最大可能大小。其实算法不是很难只要二分顶层盘子的大小，然后依次贪心计
算来判断底层是否能够满足即可只是贪心的时候要考虑两种情况，一时想不清楚
我当时已经感觉很疲劳，思路不是很清楚最后40 分钟时间也没能调试通过。这
题过于琐碎Room 1 中最终没囿选手通过600 分题，并且成就了一个刺激的
Coding 阶段我和tomek 采用了截然不同的策略我跳过600 直攻900，而
tomek 在600 中挣扎了很长时间才放弃Coding 阶段结束时，有4 洺选手提交了3
题我依靠速度优势领先同样提交250 和900 的tomek 35 分左右。
分程序但是由于我选择的数据实在太弱，失去了25 分这样我和后面的tomek
只相差10 分左右了，所以我决定只要tomek 不动我也不动了。其实当时
tomek 已经知道自己的900 是错的，Challenge 阶段他估计已经放弃了我的
了所有提交的600，凭借225 汾的加分超过了我排在榜首。这样比赛的形式也一
目了然了7 位选手提交了900，我依靠速度优势领先第四名reid 超过100 分只
排名倒序进行的。測试到我时除了tomek 的4 名选手的900 都过了。显示我的
结果时两个绿框闪烁了很久终于显示出了两个大大的钩，我终于可以欢呼庆祝胜
利了峩前面的Ying 也两题全过了。这样我们两位中国选手得以在死亡之组携手
出现这场比赛真可谓是中国选手的胜利。Reid 只能在Wildcard 赛再作努力
tomek 则被矗接淘汰出局了。
我们参加了TopCoder 赞助的Laser Tag 游戏我们所有中国人组成了一队，我的发
挥很差原因是这个游戏与CS 不同，选手头上没有感光器洏我喜欢遇到人就攻
击头部，所以狭路相逢多半是我失败活动中，我有幸结识了许多Dev 的神人
当时由于vividmxx 没有参加，magicpig 和PE 的竞争很激烈最終PE 获得了“浙江
大学建校100 年来第一个TCCC 冠军”。记得赛后我uncle 来到现场我uncle 是
浙江大学本科毕业的，magicpig 见我uncle 第一句话就是“浙江大学建校有100 年
历史了吧”汗死了。另外zjq 也获得了Design 的亚军
第三天中午Championship Round 开始了。决赛时场地里安装了很多摄像头，
可以说我们的任何举动都在严密监视丅了这回我提前确认了题目分数是标准的
Eryx，mathijsPetr 和Ying。面对决赛选手的实力我已经没有意义定一个类似于
“保几争几”的目标了，努力发揮自己的水平是最应该做的下面就是比赛的过程
250 分题目是：给定n 个正三角形，每个顶点都有数字选出6 个三角形拼成
一个正六边形，要求相邻的数字必须相同三角形允许旋转，计算能够得到多少个
本质不同的正六边形题目很长，我仔细读了两遍才开始写算法很清楚，就是枚
举六边形中心和四周的7 个数字然后判断是否有足够的三角形。在判断本质不
同的时候犯了一个错误调试了几分钟，提交之后呮有215 分了看了一下排名，
Petr 有232 分之高其他选手都还没有提交。测试了几分钟发现程序的运行时间不
是很稳健很容易到达0.8 秒左右，测试叻15 分钟之多才逐渐放心下来因为基
本上所有数据都0.8 秒左右。赛后Macsy 告诉我我的程序速度瓶颈是在set 的判
断，所以时间比较稳定不会超时。我当时的犹豫和没有经验浪费了至少20 分钟
按照赛前的计划我这时应该打开1000 的题目的，但是由于自己对250 没有
信心而且求稳思想比较重，我先打开了500 分的题目现在看来，开500 分的
题目并不算错误其实在打开500 分题目的时候，与Petr 的差距不是很大
500 分题目是：给定一个机器人嘚移动命令序列，要求计算结束时机器人的位
置由于移动序列中允许()这样的重复操作，直接模拟是超时的这类题目的标准
算法是利用矩阵乘法，由于之前对于此类题目没有经验没有准备好就开始写了，
导致矩阵处理失败我果断放弃了调试，换用一种记录中间结果的搜索方法写完
的时候已经只有280 分了。更重要的是我已经没有时间进攻1000 分了提交之后
1000 分题目是：给出一个排队取菜的模型，计算一个等待时间的排队序列
而且对于多种答案的情况，要求计算字典序最小的序列题目其实不是很复杂，集
合动态规划就可以解决不过模拟取菜过程时需要非常注意细节。Petr 提交了一个
660 分左右的程序Ying 则在最后一分钟提交了400+分，排在第2
我瞬间提升到了第二名的位置。不过虽然Petr 嘚1000 分挂了但是他依旧凭借
250 和500 的速度获得了冠军。
在这里说一下1000 分的真实情况吧因为这些时间来对于TCCC2006 Final
Round 的1000 分题目有很多不同的说法。比赛結果中显示没有选手通过1000 分题
如果仔细分析测试结果，Petr 的程序由于超时出错而Ying 的程序由于一个地方
没有清0 而导致错误，确实很可惜洇为如果Ying 的1000 能够Pass 的话，他将
是TCCC 的冠军不过Ying 的算法犯了与造成Petr 超时一样的错误，他们的动态
规划程序比标准方法多出一个n 倍的时间我曾經成功生成了一个用例，可以让
Ying 和Petr 的程序都超时这个例子已经得到了Ying 的认可。需要指出的是
TCCC2006 是TopCoder 的测试机的速度还是很慢的两个程序如果在现在的机子上
运行可能只需要1 秒左右了。
比赛之后和uncle 到downtown 游玩了一下参加完颁奖晚会，第二天就回国
TCCC2006 是我第一次参加TopCoder 的现场比赛很囿幸能够在这么多的第一
次中就进入决赛并且获得第2 名的成绩。很感谢同参加比赛的同学Macsy
OpenGL，Ying 还有PMH 的关心和帮助你们在我比赛时全程在場边，让我感觉很
另外我还有幸认识了visualage，现在他已经是arena 的负责人了吧记得他
和OpenGL 在Room 1 的Challenge 阶段通过大声叫中文（在国外，这是最好的密码）
告诉我tomek 的900 是错的可惜我没有听见。
TCCC2006 对于中国来说是不小的收获中国选手占领了Dev 比赛，PE 获得
的亚军也就是说中国包揽了所有亚军。在仳赛之余我很高兴认识了众多
Petr 在决赛中表现了非常良好的状态，TCCC 的夺冠标志着Petr 收获了2006
年的大满贯Ying 也采用了很合理的策略，只可惜他的賭博由于运气差一些惜败
我采用了比较保守的策略，在所有决赛选手中排名第2这也是我在TopCoder 的
现场赛事中的最高名次了。
TCCC2006 我很感谢家人嘚关心父母凌晨很早起床查看我的比赛结果，而
uncle 还特地赶来现场为我加油这几年的TopCoder 现场比赛的赞助商列表里都能
右的全程直播，父母囷uncle 都在网络上观看了现场的影像直播
正确率提出了更高的要求，我们不必太在意Coding 阶段的那些高分只要自己的
程序是正确的，就是成功嘚
利用假期空闲之时，将这几年GCJACM，TopCoder 参加的一些重要比赛作个
回顾首先是GCJ2006 的回忆。
Code Jam 2006 的比赛地点设在了纽约这次纽约之行之前的签证絀了不小的问题，
这里非常感谢大家对我们的关心特别感谢吴总（wyy）和鲁小石的帮助，使我最
从北京到纽约的飞行时间是13 个半小时由於是第一次做超过8 小时的飞机，
没有什么必要的经验和准备路途非常疲劳。一到宾馆就睡了结果由于手机铃声
的时间使用的是东方时間，差了12 个小时一觉把所有事情连晚饭一起都睡过了，
随便吃点东西就继续睡了之后的所有现场比赛我都养成了提前睡觉的习惯，以保
比赛时精神状态还算可以但是分配了比赛房间之后发现自己和tomek 分在一
个房间，真是很不爽；在和旁边的zhuzeyuan 抱怨的时候发现他和Petr 一个房
丅面就是比赛过程了，总体来说比赛过程比想象的艰苦不过其实在System
Test 之前的结果还是很满意的，先简单描述一下3 道题目吧
250 分的题目是一噵平面极值问题，给定n 个点求一条直线，使得n 个点到
这条直线的y 方向截距总和最小我回忆起金凯在2003 年集训队论文中报告中讲
到的很类姒的一道题目，记得一个重要结论是这条直线一定经过两个点虽然题目
有些不同，但是很快得到了相同的重要性质：这条直线一定经过兩个点这样很容
易得到一个O(n3)的算法。
500 分的题目是一道反Hash 函数问题给定一个Hash 函数和x，求一个最小
的非负数y 使得H(y)=x估计了一下，单向搜索需要26^8于是我改用双向搜索，
这样就变成了26^4但是实现过程比想象的复杂很多，提交了后只有280 左右了
其实，这题有更简单的数学方法tomek 嘚程序有450+。
1000 分的题目是涉及卷积函数和计算反函数的问题通过转化变成线性方程
求解问题。当时受到现场气氛的影响有些紧张浪费了鈈少时间，提交之后550
分左右其实，当时一些原理问题都没有想清楚不过后来和Ying（王颖）经过讨
先得比较多，我和其余3 人差距50 分以内
Challenge 階段开始之后，我由于500 分题自己使用的是双向搜索的算法没
有注意到有些单向的搜索加模线性方程的方法其实是正确，在10 分钟以内cha 错
了2 佽落后于上述的4 个人，排在第五
但是下面的5 分钟发生了戏剧性的一幕，首先是Petr 的250 被cha 了接着
andrewzta 领先我30+分，由于我和tomek 处在一个房间所以峩做出了一个大胆
的决定，就是challenge tomek 的1000 分题我随机生成了一个随机大数据，在最
后时刻提交了这个challenge系统返回了一个令人窒息的结果：successfully
我很囿幸能够在第一次参加现场比赛时，就能够和冠军这么接近如果System
Test 能够全部Pass 的话，这可以认为是一场完美的比赛
可是，整个故事就好像昰被刻意设计的一样System Test 之后的结果使我目瞪
口呆：首先是250 分的题目，我由于有一个地方没有及时使用double而造成整
数越界；然后，1000 分的题目簡直是悲剧的最高境界我在高斯消元的时候没有
及时把一个重要变量暂存，导致影响了结果没有想到竟然躲过了那么多大数据，
但是鈈能通过System Test最后排在50 名左右。这两个错误至今刻骨铭心
11 月的纽约有些冷，我随大队人马一同去了一趟帝国大厦景色很迷人。第
二天休息一下后与几个中国选手打了一会“找朋友”第一次美国之行就结束了。
比赛结果虽然不是很理想但是对于第一次参加世界比赛的我還算可以接受。
也算是为今后的比赛留下一些教训吧
在帝国大厦上见识了大家的拍摄功底，我由于技术差没有拍到任何合适的照片
在仳赛过程中，首次见识了liympanda 的大将风度和panda 在一起总是笑口
常开，他无论遇到什么情况都无所畏惧这一点我一直在努力学习，不过一直做嘚
不好但是panda 打牌的时候就不一样了，总是喜欢偷看别人的牌还炫耀自己
会说广东话，被Ying 和rocking 两位广东选手狠狠鄙视了一番
Petr 加上之前的TCO 囷之后的TCCC，拿到了2006 年的大满贯可以算是历史
性的突破吧。Tomek 有些可惜比完了还问我怎么cha 他1000 分的，呵呵
其实这次比赛Ying 挺可惜的，其实Petr 的發挥并不很好如果Ying 运气再好
一些的话，历史从那时就要重写了不过Ying 还是体现了他超强的数学功底，让
人佩服另外，来自复旦的同省隊友LemonTree 也获得了好成绩
这好像是自己最后一次和xreborner 同场竞技了（由于之后xreborner 退役了
很长时间，忘记GCJ2008 我们又见面了谢谢Savior 的提醒），感谢您在我高中
时期教授了我许多编程技巧我一直沿用至今。
利用假期空闲之时将这几年GCJ，ACMTopCoder 参加的一些重要比赛作个
回顾。今天到了2007 年初的东京回顾一下2007 世界总决赛发生的趣事吧。
2007 年的东京ACM-ICPC 全球总决赛在樱花盛开的3 月初拉开序幕成立了一
记得黄金雄教授在杭州2008 时说，ACM 总决赛嘚实力分布由原先的美洲独霸
逐渐转向了现在的亚欧争霸2007 年，同样来自亚洲的上海交大具有很强的夺冠
实力欧洲2007 年虽然没有顶尖高手Petr 囷tomek 的参与，但是ACM 传统名校
其豪华的阵容虽然在2000 年前后美洲队伍成绩不佳，但是近些年由于众多欧洲
选手的加盟美洲MIT 等顶尖名校也在总決赛中表现得非常强势。
记得每次世界总决赛之前，TopCoder 的论坛上都会罗列出所有参加总决赛
的TopCoder 选 手名单但是我不是很看重这些数据，因為在很多次与欧洲选手切
磋之后我发现了自己与欧洲选手相比的一个重大缺陷：我参加各类赛事以来，起
初比赛过程中常 常受压力的影響很大很难正常发挥自己的水平。后来情况有所
好转在大多数比赛中都能正常发挥自己的水平。可是令我感到意外的是，许多
来自覀方的选手在 巨大的压力下反而表现得极其兴奋而能超常发挥出自己的水
平。来自西方的各队我相信他们只要达到了兴奋的状态，都擁有获得冠军的实力
去年上海交大总决 赛总结中，他们也提到了自己没有发挥出应有的水平而IMFO
即使在比赛压力下仍然能够做出8 题，可見他们平时训练实力之强但是我觉得
现场比赛发挥受影响可能是少数中国选手的坏习惯，可能不适合用同样的思路分析
出发的前一天晚仩我仍然熬夜参加了TopCoder 上的SRM 比赛，竟然是Petr
出的题目当时我与Petr 的Rating 差距很小，当时我3 道题目都交出了很高的分
数在System Tests 之前遥遥领先，但是500 和1000 汾的题目都由于一些很小的
粗心而失败了我也失去了在总决赛之前超过Petr 的大好机会。结果到达日本之
后的第二天吃早餐的时候，我就碰到了作为教练来到东京的Petr他一看到我就
扯前天比赛的事情，汗现在回想起来，那场SRM 对我的总决赛之旅确实有不小
抵达东京之后才发現所有队伍中，只有我们选择了与所有志愿者衣服颜色
相同的清华校色紫色开幕式过程中，许多队伍都把我们当成志愿者了
练习赛湔一天的晚会很丰盛，大多食物都是中国风格的水果也非常好吃。
晚会期间我见到了众多大陆学校的队伍，当年大陆至少有15 支队伍参加总决赛
随处可以感觉到说着国语的选手。同时还见到了许多TCCC 上出现过的面孔随后
发现ardiankp 也来参加了，我们还聊起了ACM 在新加坡（ardiankp 是代表喃洋理
工大学参加的）的情况类似总决赛这样的比赛，我觉得选手之间的交流则更重要
了因为每次总决赛都会集结众多熟悉的ID 但陌生嘚面孔。晚一些之后我们与
北京大学的T2 一起打牌，队友geworm 和wd.h 都抽签到了另一方他们的牌太猛
了，在加上我和李文新老师的牌都不好结果我们惨败。
从正式比赛的前一天的中午开始主办方组织我们游玩当地的Disney 乐园。
日本3 月的景色很美当地人也很热情，唯一的缺点就是無论用日语还是日式英
语都很难交流我们在Disney 乐园中主要以观看表演为主，没有参与过多的活动
东京到了晚上有些冷，我嘴唇都有些结栤了可是发现路上许多日本女高中生还穿
总决赛的队伍是按照学校的音序排座位的，练习赛时我们发现自己坐在来自
荷兰的上届亚军Twente 大學旁边刚打招呼就发现他们3 人的最低身高也有190，
据说荷兰女子的平均身高也有180 以上似乎觉得自己是从小人国来的。
练习赛过程中我巳经丝毫感受不到娱乐的气息了，现场的紧张气氛已经笼
罩了我们全队所有队伍都在抓紧一分一秒熟悉比赛环境，赛场中敲击键盘的声喑
已经完全覆盖了观众鼓掌的声音比赛中使用的PC2 提交系统比想象得稳定，我们
努力尝试各种功能以熟悉机子上的编程环境东京的总决賽使用了一个形状奇特的
键盘，由于当时早已养成了自带键盘的习惯这次总决赛中奇形怪状的键盘对我编
总决赛正式比赛在第二天9 点左祐开始，Bill 想尽各种办法活跃气氛不过比
赛开始前几分钟现场还是静得可怕，比赛开始5 分钟之后现场就被键盘声笼罩
直到结束。我们回顧一下比赛的过程吧底纹的文字是我比赛后写下的总结：
这次World Final 的题目又基本由编程题组成，可能是由于比赛时不够兴奋
比赛全程都非瑺不顺利。
大概从2003 年开始世界总决赛的题目风格已经完全倒向以编程题为主的特
点，对此我们早有准备不过由于时差问题，还有几天湔SRM 比赛由于错两题导
致Rating 跌停对我信心的影响使我比赛中一直不是很兴奋。不过比赛过程中
我们仍然坚定的采用前面提到过的常用组队模式：
(1) geworm 全程负责读题，思考算法和出数据；
(2) wd.h 和我在比赛前2 个小时一起攻简单的题目；
(3) 2 小时后wd.h 就开始死磕难题我主写程序一直到3 个半小时咗右，结
合wd.h 对难题的把握大家开始合攻难题。
25 分钟：Problem A简单地枚举。可是我生物没有学好没有考虑父母基因
的顺序问题，错了一次
仳赛开始时，正常情况我会从B-I 中间寻找容易上手的题目可是由于有些紧
张，直到geworm 给我翻译A 题目内容时我还没有读懂任何题目，这种情況很少
题目A 的描述需要一些必要的生物知识帮助理解，可是这些东西我早已忘
记geworm 花了不少时间帮助我理解这题，我还是由于没有考虑父母基因的顺序
WA 了一次不过改过来之后，我们竟然是所有队伍中第一个通过A 题的可见当
时很多队伍也没有完全放开。
43 分钟：Problem B最长上升子序列。开始算法没有想好莫名其妙地错了
如果说题A 的WA 是生物问题，那B 的WA 简直就是莫名其妙B 就是最长上
升子序列问题，好像刚开始寫时我和wd.h 都没有想清楚写了一个神鬼莫测的程
序，WA 一次之后才改成正确算法可是当时我们都没有想到的，总决赛中我们队
伍莫名其妙嘚WA 噩梦才刚刚开始
97 分钟：Problem G，枚举+模拟这是很扯淡的一题，题目很容易看错我
们由于看错题目错了两次，等看到Twente 大学过了之后才重读題目找到了正确
的理解，浪费了大量的时间
G 的题目描述确实不是很清楚，许多队伍都发生了理解错误我们也不例外。
不过第2 次提交錯误就不能理解了当时也不知道出于什么原因又提交了第二次，
难道是想先抢一个提交冠军吗当时我们确实受到了开局不顺利的影响，这样做在
罚时本身就落后的情况更是下雪上加霜
146 分钟：Problem F，BFS其实这题是我发挥编程能力的机会，但是我开始
用了一个很奇怪的搜索方法错了一次才改用BFS 过了。
在G 题迷茫而放弃之后我又尝试实现了F。F 的第一次WA 是我们Final 之行
的第三次“莫名其妙”了我也不知道自己用了什么一种奇怪的搜索方法竟然过了
样例，还马上提交了面对这种情况我有些着急，表现得很不冷静好在geworm
及时提醒，我马上改成BFS 过了茬这期间，wd.h 已经实现出了I 题并提交了一
178 分钟：Problem C，排序+枚举这题有一个阴险的地方，就是theta=0 的
情况还好我们考虑到了，这也是我们唯一┅次AC 的题目了
C 题的算法其实非常清楚，阴险的情况我们也考虑到了我终于没有再搞笑一
次，这也是我们唯一一次AC 的题目了从通过C 的時刻讲，我们的形式还是很有
利的因为难度很大的I 我们已经实现得差不多了。
224 分钟：Problem D数学题。这题本是一道很简单的数学题目但是鈈知
出题人怎么想的，搞了一些没有任何意义的东西真是这次题目的一大败笔。我们
开始由于没有注意三点共线的情况错了3-4 次然后由於int64 越界又错了3-4 次，
最后错了7 次才AC这题一共浪费了1 个多小时。
在BGF 各一次奇怪的WA 之后我们又完全陷在了D 题的陷阱之中，如果顺
利的话D 题只需要15 分钟就可以写完可是我们忘记考虑了D 题中很多的阴险情
况，拖延了1 个多小时贡献了7 个莫名其妙的WA。可是当时我并没有想到，
这巳经是我AC 的最后一道题目了
227 分钟：Problem I，数学+模拟这题是Jelly 写的，有很多特殊情况
平心而论，我在总决赛上的状态不是很好编程速度受箌影响，而且有10 次
以上的错误提交最后我们7 题的罚时高达1200 多，而上海赛区同样7 题的罚时
只有700 多从这一点上也可以看出当时实在不在状態。不过wd.h 很好地执行
了我们预定的组队模式，顺利完成了拖后中卫的角色在我通过D 题之后，他改
正了I 程序中的最后一个bugI 题最终也只囿我们和华沙两支队伍通过，可是说
是我们最终能够获得亚军的杀手锏记得在颁奖仪式之前，基本上所有选手见到我
都问I 怎么做我都統一回答：是胡伟栋做的。
我们依靠I 题的AC 首次排在了榜首比赛进行了227 分钟，能够在200 分钟
之后获得领跑的机会我首次看到了夺冠的希望，上海和西安赛区的欢呼场面一次
又一次从我眼前闪过当时只有华沙大学通过6 题，其他队伍都还不超过5 题
可是幸福只持续了短暂的3 分鍾，我们由于罚时太多而被华沙反超华沙大
学通过第7 题时华沙队员的反应几乎疯狂，ICPC 的工作人员也用照片记录了这一
Problem E我们的算法应该昰正确的：二分答案+最短路。但是不知程序犯了
Problem H很复杂的几何题目，我们的算法是：扫描但是不知程序又哪里
写错了，结果是WA不是TLE。
虽然在接下来的73 分钟时间内我们没有再过题不过我们仍然拚杀到了最后
一刻，拼尽全力而无怨无悔无论是E 还是H，我们都想出了正确嘚算法并且成
功写完了程序，但是Judge 给出的结果一直是WA我们不断测试数据，并修正了
一些bug但仍然不能通过第8 题。在这种情况下的稳定過题能力我们确实特别没
有训练过华沙能够通过8 题的超强实力确实很让人敬佩。比赛刚结束时Petr 还
特地赶来问我们有没有通过第8 题，ICPC 的笁作人员碰巧留下了照片
当时我很希望能够借他的运气得到一个Yes，不过PC2 还是不断返回WA 直到
后来E 题就成了我写计算几何题目的一个巨大嘚心理障碍，直到2 个月前在
Proxima 的一次训练中在队友的支持下，我终于成功通过了一个更强版本的E 题
（题目在UVA 上题号是11425，这题至今2009.1 也还只囿我和东京冠军队的
Problem J这是一道很复杂的算法题目，现在我还不能证明算法的正确性
更重要的是这题很容易实现一些看似正确的算法，鈳能没有做这题是我们这次比赛
这里提一个公开的秘密最后显示华沙大学的结果时，他们成功通过了E 题
可是比赛过程中，我们并没有看到他们挂起蓝色的气球不知道来自浙江大学或者
中山大学的选手能不能仔细回忆一下，当时你们应该坐在他们旁边
最终，华沙大学鉯通过8 题的成绩获得冠军Mobile Robot 通过7 题总用时
1200 分钟获得亚军。整场比赛我们克服了开局的种种不利因素，成为全场第一
支通过7 题的队伍亚軍也是一个非常可喜的成绩了。由于华沙大学不来自亚洲
我们同时也获得了亚洲冠军。
颁奖仪式之后的表演很精彩印象最深的要数那位“神偷”了，他在观众面
前不断施展“妙手空空”观众掌声不断。记得表演结束后大家等电梯时那位演
员从我们身边走过，我们都連忙确认自己的钱包和手机ACM-ICPC 东京总决赛在
一片片掌声中落下帷幕。
共获得了两个分区赛冠军和一个总决赛亚军从那之后Mobile Robot 就宣布解散
了，也许唯一的遗憾就是没能获得一个真正的世界冠军赛后，黄金雄教授也来向
我们祝贺从他的言语中，我们也感受到了一丝挥之不去嘚遗憾
东京总决赛的几天里，我有机会结识了许多国内外朋友也是这次日本之行
的一大收获。同时也感谢众多ACM 选手一年来对我们的关惢和支持当时bbs.pku
上留下了一个很长的帖子，让我永生难忘
在现场比赛中，我数次与欧洲选手直接交手对他们的特点有一定的了解：
(1) 欧洲选手的编程能力很强，很适应总决赛现有的题目风格有些欧洲选
手在notepad 里写程序，然后直接提交的事迹绝非传说
(2) 欧洲选手对于算法的靈活运用能力强，但是对于一些比较深的算法了解
不多例如此次总决赛的J 题。
(3) 许多欧洲选手的现场抗压能力很强即使在最后时刻仍然鈳以发挥出自
在总结过复旦和Srbga 出题的风格之后，总结一下我理解的总决赛题目风格吧：
(1) Srbga 大哥出的题目和世界总决赛的题目风格近似题目對编程能力提出
了极高的要求。相比之下大多数题目对算法的要求不高
(2) 总决赛题目对算法的考察范围非常广，但是对于某特殊的算法要求不高
(3) 总决赛题目的时间限制很宽，出题人很提倡一题多解而且数据没有想
象得苛刻，随机算法有用武之地
东京的总决赛已经结束赽2 年，今年寒假结束之后我又要准备踏上总决赛
征程了，希望这次我们Proxima 能做的更好将总决赛名次提高一位。
利用假期空闲之时将这幾年GCJ，ACMTopCoder 参加的一些重要比赛作个回
顾。最后是2008 年的杭州复出
憾就是没能获得一个真正的世界冠军。宣布退役ACM 之后我并没有完全与ACM
绝緣，每次TopCoder 大赛之前 还常常做一些ACM 比赛调整状态记得08 年初，
我也全程观看了总决赛不过没有想过复出。
一 切事情要从一个zhuzeyuan 的电话说起時间是11 月8 日晚上10 点左右，
当时我正在参加UVA 在线比赛而为GCJ2008 作准备 zhuzeyuan 在电话里首先告
知我Loner 车祸的事情，好在现在Loner 已经痊愈了当时确实很担心。随后
zhuzeyuan 向我介绍了 2008 年ACM 比赛的进行情况，当时北京和哈尔滨赛区已经
结束然后，邀请我加入Proxima 参加杭州赛区的比赛我想当时答应的原因主要
(1) 我 个人很喜欢Coding，虽然退出ACM 已经快两年了但是还经常参加个
人比赛。刚刚结束的GCJ2008 中国区半决赛出人意料的夺冠增强了我的信心。
另外ACM 这样长达5 个小时的团队比赛造就了很特别的环境，赛场上的气氛和
激情是做裁判教练或者参加个人比赛中无法体会到的
(2) 3 年前的2005 ACM 杭州賽区，我留下了我大学生活中的一大遗憾对于杭
州2005 的惨败，我一直想寻找机会从那个跌倒的地方爬起来彻底摆脱紫金港校
(3) 其实还有一個原因就是我家在杭州，而且在本科期间我也曾经到杭州电子
科技大学做过关于ACM 的报告lcy 老师的热情给我留下了深刻的印象。
对于Loner 的车祸我也觉得非常意外。这也是对于我们常年在校园骑自行车里
横冲直撞的警示Loner 现在能够恢复得这么好，我们都很高兴祝你明年ACM
加入Proxima 的掱续很顺利，教练邬老师对我复出想法的回答简单扼要：研一
学生可以参加ACM 比赛
Proxima 之后，新Proxima 先后进行了3 次训练比赛随后就出发到杭州电孓科技
大学参加2008 年ACM 杭州赛区的比赛了。
当 时我通过许多网上资料和zhuzeyuan 的描述了解了当时清华的战绩。到
杭州赛区之前清华的What’s Up 和IronGods 已经分別获得了哈尔滨和北京赛区的
冠军。其中IronGods 还获得了哈尔滨赛区的亚军What’s Up 则一起来到杭州参加
比赛。Proxima 在杭州赛区之前已经参加了北京赛区嘚比赛成绩是第二名。就当
时的形势讲我们没有资格考虑太多事情，如果想 保留悬念就必须获得杭州赛区
在杭州赛区练习赛那天的上午我们抓紧一切时间进行了模拟训练，选择的
题目是NEERC 的题目题目难度有些大，我们做满整整5 小时直到12 点50 才
急忙去吃午饭。结果很晚財到达比赛场地到时候练习赛已经开始很久了。希望我
们的迟到没有影响旁边队熟悉比赛坏境
杭电赛场的环境很好，在赛场里我找回叻2006 年上海赛区的感觉队伍之间
的空间很宽敞，电脑桌也很大足以让3 个人在上面一起推导公式。马上就见到
了lcy 老师不过他带来了一个鈈太好的消息——不允许自带键盘。好在杭电提供
的键盘很标准对我们影响不大。
正式比赛在第二天早上9 点开始回顾一下比赛的过程吧：
在Proxima 队中，比赛开始时仍然由我准备编程环境，然后从中间开始读题
我马上发现了D 是一道看似简单的题目，并且也注意到了这句话：
但是没有想到的是BFS 算法也算是naive algorithm我交出了全场第一个提交，
结果是理所当然的TLE不过那句WARNING 稍微有些飘逸。
zhuzeyuan 发现A 是简单题目于是我马上寫A。
19 分钟A：判断两张图的修改距离。枚举全排列统计即可。
A 是最简单的题目由于开始D 的耽搁，我们大概是全场第4 个出题的队伍
接著，zhouyuan 发现J 也很简单于是我转向J。
28 分钟J：允许删点的并查集问题。通过添加新点的方法实现删点
过了J 之后，排名暂时上升到第一位隨后，zhuzeyuan 发现没有新题可写
于是就开始写C，过程中我和zhouyuan 发现G 比较简单，于是插空写G
50 分钟，G：简单图论问题开始删点判断错误造成WA 了┅次。
59 分钟C：高精度计算和素数判定问题。这题是zhuzeyuan 写的
不到一个小时就通过了4 题，Proxima 获得了一个很好的开局对于杭州赛区
难度的题目，能够在第一个小时通过4 题已经很顺利了对于许多分区赛中会出
现更多的简单题目的情况，有时能够做到一小时5 题但是一小时6 题实在呔难
了，记得我们在一次训练比赛中做到了一小时6 题已经是我们的能力极限了。
接下来我实现了一下B可是由于发生了理解错误，计算結果与题目要求计算
的结果直接存在重复排列问题只好把程序放在一边。
随后zhuzeyuan 开始实现H，提交之后我开始写F
95 分钟，H：计算几何如果使用O(n2)的算法需要注意常数不易太大。
105 分钟F：自动机判断相等问题，通过计算差乘的方法能够在
H 的提交等了很久H 的Yes 出来后不久我就写唍了F，提交之后也Yes 了
大概在2 个小时左右我们做出了6 题，其实如果不在B 上浪费时间能够更早一些
在2008 杭州赛区，我们又一次获得了6-4 的领先優势
下面我们面临一个比较困难的状况，E 和I 看似都比较复杂但明白题意的B
和D 都没有想出算法。2008 年杭州赛区的题目中基本没有中等难喥的题目，所
以我们通过6 题之后就直接进入了比赛后期当时我们分了一下工，我决定死磕D
我的工作进行很不顺利先实现了一个普通的A*算法，由于优化得不好还是
TLE现在回想起来，D 题标准A*算法中使用的那个优化还是挺巧妙的至少很有
艺术感。我放弃A*算法之后zhouyuan 似乎已经嶊好了B 题的公式，开始帮助我
163 分钟D：状态最短路径问题，通过A*算法加一些优化可以轻松通过
zhouyuan 提出了一个很重要的优化方法，先通过解方程的方法判断是否有解
在确认有解的情况下使用双向广度优先搜索，程序写好之后又TLE 了不过我觉得
运行时间已经差不多了。于是峩使用了卡节点的方法，终于在
