爱华网ACM2006 之后，今天简要回顾一下国内个人赛场吧。
国内个人赛场 —— 百度之星
国内个人赛场中最重要的比赛要数每年一度的百度程序设计大赛，到今年为止已经举办了 4 届，每一届我都全身心地参加了比赛的
全过程，百度程序设计大赛是中国举办的规模最大的公开程序设计比赛，其参加人数比许多世界范围的程序设计大赛的人数还要多得
多。另外在 2006 年初， Google Beijing 举行了 Google Code Jam China 的比赛，刚刚开始参加TopCoder 的我也加入了这次
GCJC 之旅。
第一届 baidu 程序设计大赛：
最早的国内个人程序设计比赛要回忆到 2005 年 9月开始的第一届百度程序设计大赛了，源于宿舍走廊中的海报，我以尝试的心态
报名参加了第一届百度程序设计大赛。每一届百度程序设计大赛都由初赛，复赛和现场决赛组成。
第一届百度程序设计大赛中，印象最深的复赛题目就是那道规模巨大的最小树形图问题了， 100000的数据规模吓退了不少选手，我
鼓足勇气提交了一个理论上能够运行的程序，顺利通过了复赛进入决赛。最小树形图算法在大多图论书上就接在最小生成树算法后面
，但是其程序量远比最小生成树大，而且用途没有最小生成树广泛，在大多数竞赛中很少出现。我最早接触最小树形图算法是在
2003 年 4 月，当时正在复旦大学训练，记得关于这个问题和 xreborner讨论了很长时间才得以证明算法的正确性并实现出高效的
程序。
现场决赛于 2005 年 10 月底在北京举行，由于当年比赛的知名度不高，时间上还和 GCJ冲突，没有太多的顶尖高手参加。清华大
学除我之外只有 superzn （张宁，我们留 shell 一个人参加 ACM 北京赛区预赛 L ），当时 OpenGL还是以高中生身份参加的，还
有复旦大学的 xreborner 和 young （李阳）；中山大学的 magicpig ， Savior和张子臻（不好意思，我不记得您的 ID 了，好像
杭州 2008 的时候我们还说起此事）。我一直认为，现场比赛过程的一个重要的意义在于提供了一个老朋友重逢和结实新朋友的机会
，选手之间的交流是比赛中最重要的组成部分之一，我很有幸能够在这些比赛中认识了众多牛人。
稍微回顾一下决赛的题目吧：决赛的题目是经典的 8 数码问题，给定初始状态和结束状态，计算最短需要的转移步数。对于分数相
同的情况，按照程序的运行速度排名。比较容易想到的方法有：
(1) 单向 BFS ：最坏情况需要 1s 左右。
(2) 双向 BFS ：如果先判断无解情况，这是 xreborner 使用的方法，平均情况大概 0.002 秒左右。
(3) A* 或者 IDA* ：先判断无解情况，然后通过距离启发函数搜索。平均情况大概 0.002 秒左右。我当时使用了 A*的方法，但许
多地方的实现不是很合理。
(4) 常量表，这是最有挑战的方法，因为决赛的提交量限制在 64K 以内。
现场比赛中， (2) 和 (3)的使用人数比较多，速度相差无几，选手之间比拼的是各种细节和常数的处理。后来，我想出了一种速度
非常快的方法：
首先使用 A* 加上 “ 卡节点 ” 技术，就是限制 A* 算法搜索过程中每层的节点个数上限，这种算法扩展节点个数在 100左右。
然后，由于上述算法的正确性不能保证，把所有反例打成常量，程序大概 50K 左右。很容易发现，这个程序的速度远比比赛过程中
所有程序的速度都快得多。
最终我的程序以总时间 0.022 秒获得冠军， xreborner 和 Savior 以 0.026 分并列第二名。xreborner 的程序很可惜，如果加入
了无解判断，速度应该比我程序块， superzn 就更可惜了， superzn 的飘逸程序其实只有 0.020秒，但是有一个数据错了。
记得颁奖之后，主持人邀请获奖选手发言，选手可以通过向前走一步选择优先发言。这时，我突然感觉大家把目光都聚焦到了我身上
，向右一看，由于我站在最左边没有注意到右边的情况，可谁知其他选手都后退了一步，把我留在了看似向前一步的位置。
第二届 Astar-baidu 程序设计大赛：
第二届百度程序设计大赛没有等到 10 月，而是在 2006 年 6月就拉开序幕。没有想到的是，第二届百度程序设计大赛竟然以我在
一年前比赛中使用的 A* 算法的名字命名，感到非常荣幸。
记得复赛的题目非常正式，印象最深的要数 xreborner 招牌式的 Zuma，我推了两个小时公式才得到了正确的动态规划方程，实现
之后还由于 TLE 只有 30 分 (100 满分 ) 。还有 Ying出的无向图最小割问题，我用网络流算法又超时了。不过最后一题，我的程
序竟然比 xreborner 优化过的标程还快，真是不容易呀。清华的舍友 RealPlayer在复赛中表现很兴奋，可惜由于一个很小的错误
没能进入决赛。
参加第二次百度决赛的选手中有许多熟悉的面孔，清华的同学包括 shell ， OpenGL ， lympanda 还有 Macsy。复旦大学也来了很
多选手，其中除了 LemonTree 和 Topkiller （沈毅）之外，还有我刚到复旦时见过的 admin 和 funny的身影。另外 magicpig 和
flymouse 也参加了，而且 magicpig 和我住一个房间，吃饭时记得他把桌上所有人的 Dev 功底全都鄙视了一遍，可惜 PE不在场呀
。比赛前还看到了 Srbga 的身影，据他说是被邀请一起来玩的，其实稍微用小脑判断一下就知道一定是参与出题的，有了 Srbga的
加盟，相信决赛题目绝对不会是一年前的风格了。
第二年决赛的题目是：著名的俄罗斯方块。写程序玩一个 10 列的标准 2 维俄罗斯方块游戏。
Srbga 设计了很有特色的记分方法和评分标准。对于记分方法，特别的地方是消去 1 行后没有得分，而同时消去 2 ， 3 ， 4行的
得分分别是 3 ， 6 ， 10 ，记分方法非常鼓励一次消去多行。评分标准则更奇怪了，有 50种不同规模的数据，对于每组数据对所
有选手的得分进行排名，前 8 名的选手依次得到 10 ， 7 ， 6 ， 5 ， 4 ， 3 ， 2 ， 1分，也就是说，是存在可能性在测试结
束之后分数仍然为 0 的。
比赛过程中，我花了许多时间来分析这个奇怪的评分标准。
对于这种评分标准，常见的策略有两大类： (1) 所有数据的成绩比较平均 (2) 在一种数据风格中特别突出呢。
根据数据描述， 50 个数据可以分为 10 种不同的风格。参加比赛的总共有 50名选手，如果所有分数是完全平均分配的话，分数是
31 分，这个数字意义不大。但如果设想分数的 80% 会分配在前 10名中（根据当时选手的水平，这个假设还是比较合理的），这样
前 10 名的平均分数是 124 分左右，也就是说如果想挤进前 4 ，至少也要 100 分以上，如果想争取冠军估计需要 200分左右。如
果选择一种策略，使得它只在一种数据风格中特别突出，分数只有可怜的 50 分，而且很可能有许多有同样想法的选手，所以 (2)
不太可取。
在决定选择比较平衡的策略 (1) 的之后，需要再考虑一个问题，如果最终目标是 150 分，那么平均分数只需要 3分，也就是说每
个数据可以允许有 5 名选手超过自己。这些必要的分析帮助我明确了努力的方向，面对这种开放性的题目，多分析题目的特点往往
可以达到事半功倍的效果。
还有一个重要环节是调整估价函数，机器学习其实是一个很好的策略，可惜我当时不会。其实当时我做的事情，本质上就是人工模拟
机器学习，手工调整了 1 个半小时，眼都花了。而且我犯下了一个致命的错误，记得记分方法非常鼓励一次消去多行，也就是说对
于平坦的数据，一次消去 1-3 行的权值应该可能设置为负数，而我只把他们设成了 0 ，使得程序对于平坦的数据分数不高。Macsy
就考虑到了这一点，只可惜一个很奇怪的技术问题（在 Linux 和 Windows 下的 CLOCKS_PER_SEC参数是不一样大的，想使用卡时策
略时千万不能事先把这个数字取出来设置成 CONST ）使得 Macsy 没能成功。
由于 Macsy 和 LemonTree （同样的技术问题）的出局，我在许多数据中得到了很高的分数，最后的总分达到了是 255，领先了第
2 名有 99 分之多。其实现场的许多选手的程序风格相差并不大，可能我唯一多做的事情就是建立了一个博弈树，多搜索两层，这样
比直接贪心的程序看得更远一些。后来事实也证明了，排名靠前的选手大多都是比较平衡的策略。记得 lympanda 洋洋洒洒写了
1800 多行程序，在其中一种数据中拿到了满分 50 分。不过可惜 panda 的程序平衡性稍差，总排名进入了前 10，但最终只有三等
奖。
第二届 astar-baidu程序设计大赛，复旦大学获得了丰收。记得许多复旦的选手由于考试提前回到学校，颁奖仪式的时候二等奖颁
奖一片空场。
比赛的住宿条件可以用无与伦比来形容，很感谢 baidu 的大方与细心。记得第一天晚上还有机会和 Ikki一起打沙壶球，面对球风
完全对立的 Ikki 玩得很开心。
Google Code Jam China 2006
大概是 2005 年末，突然看到了名为 GCJC 的比赛，而且使用的是 TopCoder的比赛模式，于是就报名参加了。当时估计只参加过几
场 TopCoder 的比赛，帐号还是蓝色的， GCJC第二轮预选赛由于经验不足差一点就被淘汰了。好在有惊无险地进入到了北京的现场
赛。
GCJC 现场的选手中，我觉得至少认识 80% 吧，清华同学就有 7 人： b142857 ， fuwenjie ， lympanda， Macsy ， zig 还有
hyyylr （李老师），复旦的 LemonTree 和 TopKiller 也都来了，浙大也来了许多 TopCoder 上的元老xuchuan （徐串），
sghao126 。
记得，就在 GCJC 决赛的前一天晚上，我参加了 TopCoder 的 SRM 比赛，第一次踩住了 Petr ，不过也消耗了太多的RP 。晚上的
SRM 比赛中没有人过 3 题，第二天早上 lympanda 还把我们统统鄙视了一遍。随后， b142857 还描述他Challenge 过程中的囧事
，由于 500 分题目的返回结果需要使用 long long 类型，所以 b142857 看到一个人提交的程序计算过程中只使用了long 就果断
Challenge 了，结果失败了两次之后才发现，那个人用的语言是 Java 。
比赛中 250 分题目，简单的概率问题。我写完就交了 224 分，竟然是所有选手中最快的。后面的 500分，我虽然提交是最快的，
不过没有考虑一种情况。打开 1000 分题目之后网络就开始很不稳定了，时断时连， 1000分题目其实算法很清楚，由于网络原因提
交只有 600 分左右了。
Challenge 阶段开始时，我打开了房间中 lympanda 的 500分程序，发现我们两人的程序基本过程完全一样。又打开了一个，也一
样。但是在还没有反应过来的时候， lympanda 的 500 分程序被 Challenge 了，接着我的 500 分也被Challenge 了。然后就没有
什么斗志了，在无奈中等待比赛结束。
比赛结束之后的午饭过程中，我正好坐在 Google 中国掌门人李开复旁边。午餐快结束时，李开复问起 2个月前的百度程序设计大
赛，突然，鬼使神差地直接问我百度大赛的冠军是谁？这可是在 Google的老巢呀，抖死了。我当时真害怕他听完回答之后直接把我
赶下桌 。
好在我的 250 分和 1000 分都 Pass 了，由于 TopKiller 的 1000 分超时了，我获得了第 3 名。冠军xuchuan 和亚军 b142857
都顺利通过了 3 题。
POJ Monthly Contest
大概是从 2004 年 8 月开始， POJ 上开始举行每月一次的有奖月赛。 2005 年的月赛中，每次都有机会同 xreborner， Ying 等
高手切磋技艺。从 2006 年初开始，我已经比较熟悉了比赛的题风，连续获得了许多次比赛的冠军，并且保持了良好的个人比赛状态
。
记得 2006 年 4 月底，在 POJ 的邮箱里突然发现了 hawk 的信，他问我五一长假回家的情况。我告诉 hawk自己定在周五晚上出发
。于是，第二天早上就看到比赛安排中： 2006 年 5 月份月赛安排在了周五晚上，太囧了。
后来， POJ 上直接出现了一系列奇怪的定义，但其实结论就是我不能以正式身份参加月赛了。现在这些定义早已成为笑料了，但是
我不参加月赛之后，仍然有 ahyangyi 这样的选手夺走了绝大多数的冠军。
后两届 baidu 程序设计大赛：
从第二届开始，我们习惯了在每年 6 月等待 astar-baidu 的开赛。 2007 年最出乎意料的就要数 CS这个决赛题目了，我在关键的
买枪环节犯了重要错误，太迷恋 AK47 了。祝贺师兄 lympanda ， Macsy 还有 shell，不愧是真金不怕火炼。
第四届百度大赛我参与了预赛和复赛的命题工作，但是没有参与决赛的命题。决赛题目是一道关于直升机的题目，印象最深的是
ahyangyi使用了一个很有进攻性的策略，如果采用淘汰赛，可能就是冠军了。对我来说，通过现场比赛，有机会和老朋友重逢，并
结识了许多新选手是我最大的幸事。
利用假期空闲之时，将这几年 GCJ ， ACM ， TopCoder 参加的一些重要比赛作个回顾。今天到了 2007年初的东京，回顾一下
2007 世界总决赛发生的趣事吧。
ACM-ICPC World Final 2007 —— Mobile Robot 东京决战
2007 年的东京 ACM-ICPC 全球总决赛在樱花盛开的 3 月初拉开序幕。成立了一年的 Mobile Robot 凭借 2006年 ACM 上海赛区的
冠军，代表清华参加了此次 ACM 盛会。
记得黄金雄教授在杭州 2008 时说， ACM 总决赛的实力分布由原先的美洲独霸逐渐转向了现在的亚欧争霸。 2007年，同样来自亚
洲的上海交大具有很强的夺冠实力，欧洲 2007 年虽然没有顶尖高手 Petr 和 tomek 的参与，但是 ACM 传统名校 St.Petersburg
， St. Petersburg IMFO ， Warsaw ， Saratov ， Petrozavodsk等都派出了极其豪华的阵容。虽然在 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 题，并提交了一次，结果是 WA 。
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 程序中的最后一个 bug 。 I题最终也只有我们和华沙两支队
伍通过，可是说是我们最终能够获得亚军的杀手锏。记得在颁奖仪式之前，基本上所有选手见到我都问 I 怎么做，我都统一回答：
是胡伟栋做的。
我们依靠 I 题的 AC 首次排在了榜首。比赛进行了 227 分钟，能够在 200分钟之后获得领跑的机会，我首次看到了夺冠的希望，
上海和西安赛区的欢呼场面一次又一次从我眼前闪过。当时只有华沙大学通过 6 题，其他队伍都还不超过 5 题。
可是幸福只持续了短暂的 3 分钟，我们由于罚时太多而被华沙反超，华沙大学通过第 7 题时华沙队员的反应几乎疯狂， ICPC的工
作人员也用照片记录了这一时刻。
Problem E ，我们的算法应该是正确的：二分答案 + 最短路。但是不知程序犯了什么错误，没有 AC 。
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 也还只有我和东京冠军队的marek 通过）。
Problem J，这是一道很复杂的算法题目，现在我还不能证明算法的正确性。更重要的是这题很容易实现一些看似正确的算法，可能
没有做这题是我们这次比赛的唯一成功之处。
I 的算法大致如下：
(1) X_i = the mininum cut between V_i and V_0.
(2) while (the graph is not empty)
{
(3) m = min(X_i).
(4) remove all nodes V_i whose X_i=m.
(5) let X_i = min( X_i , m+ the mininum cut between V_i and V_0).
}
(6) return X_1.
这里提一个公开的秘密，最后显示华沙大学的结果时，他们成功通过了 E 题，可是比赛过程中，我们并没有看到他们挂起蓝色的气
球，不知道来自浙江大学或者中山大学的选手能不能仔细回忆一下，当时你们应该坐在他们旁边。
颁奖：
最终，华沙大学以通过 8 题的成绩获得冠军， Mobile Robot 通过 7 题总用时 1200分钟获得亚军。整场比赛，我们克服了开局的
种种不利因素，成为全场第一支通过 7 题的队伍，亚军也是一个非常可喜的成绩了。由于华沙大学不来自亚洲，我们同时也获得了
亚洲冠军。
颁奖仪式之后的表演很精彩，印象最深的要数那位 “ 神偷 ” 了，他在观众面前不断施展 “ 妙手空空 ”，观众掌声不断。记得
表演结束后大家等电梯时，那位演员从我们身边走过，我们都连忙确认自己的钱包和手机。 ACM-ICPC东京总决赛在一片片掌声中落
下帷幕。
总结：
ACM-ICPC 总决赛结束后， Mobile Robot 又恢复了平静。 Mobile Robot成立以来共获得了两个分区赛冠军和一个总决赛亚军，从
那之后 Mobile Robot就宣布解散了，也许唯一的遗憾就是没能获得一个真正的世界冠军。赛后，黄金雄教授也来向我们祝贺，从他
的言语中，我们也感受到了一丝挥之不去的遗憾。
东京总决赛的几天里，我有机会结识了许多国内外朋友，也是这次日本之行的一大收获。同时也感谢众多 ACM 选手一年来对我们的
关心和支持，当时 bbs.pku 上留下了一个很长的帖子，让我永生难忘。
在现场比赛中，我数次与欧洲选手直接交手，对他们的特点有一定的了解：
(1) 欧洲选手的编程能力很强，很适应总决赛现有的题目风格。有些欧洲选手在 notepad里写程序，然后直接提交的事迹绝非传说
。
(2) 欧洲选手对于算法的灵活运用能力强，但是对于一些比较深的算法了解不多。例如此次总决赛的 J 题。
(3) 许多欧洲选手的现场抗压能力很强，即使在最后时刻仍然可以发挥出自己的水平。
在总结过复旦和 Srbga 出题的风格之后，总结一下我理解的总决赛题目风格吧：
(1) Srbga大哥出的题目和世界总决赛的题目风格近似，题目对编程能力提出了极高的要求。相比之下大多数题目对算法的要求不高
。
(2) 总决赛题目对算法的考察范围非常广，但是对于某特殊的算法要求不高。
(3) 总决赛题目的时间限制很宽，出题人很提倡一题多解。而且数据没有想象得苛刻，随机算法有用武之地。
东京的总决赛已经结束快 2 年，今年寒假结束之后，我又要准备踏上总决赛征程了，希望这次我们 Proxima能做的更好，将总决赛
名次提高一位。
利用假期空闲之时，将这几年 GCJ ， ACM ， TopCoder参加的一些重要比赛作个回顾。今天总结一下国际个人赛场吧。
国际个人赛场 —— 三大赛事
ACM-ICPC 总决赛结束后， Mobile Robot 就宣布解散了，也许唯一的遗憾就是没能获得一个真正的世界冠军。宣布退役ACM 之后，
我仍然连续参加了那之后的每一场世界范围的现场编程比赛，按照时间先后分别是： TopCoder Open( 简称 TCO)2007 ，TopCoder
Collegiate Challenge ( 简称 TCCC)2007 ， TCO2008 以及 Google Code Jam(简称 GCJ)2008 。每次比赛，我都度过了一段美好
快乐的时光。
TopCoder 公司与三大赛事：
TopCoder 公司大概在 9 年前成立，成立的原因有些让人匪夷所思，据说公司创立者原来是另一家 IT公司的大股东，在把原来公司
的股票转手之后换了一笔钱，开设了 TopCoder 公司。然而 Topcoder 和原来的 IT 公司有一个重要协议，就是Topcoder 在创立之
初的两年内不得从事软件开发的工作。于是 TopCoder 在前两年时间内以类似竞赛的方式从事软件开发的活动。经过 9年的发展，
现在 TopCoder 公司已经基本由算法竞赛转向软件开发了。
TopCoder 公司除了在网上举办 SRM 之外，每年还举办 TCO 和 TCCC 等现场赛事（当然还有 TCHS，不过规模比较小，参与面也不
是很大）， TCO 和 TCCC 分别在每年的 6 月和 11 月举行，每次大赛都能汇聚众多国际编程高手。另外， Google 公司从2000 年
开始，先在各大洲举办名为 Google Code Jam 的比赛，从 2002 年开始也举办全球范围的 Google Code Jam。于是这些年来，大家
一直把 TCO ， TCCC 和 GCJ 称为三大赛事。
2007 年之前的 GCJ 都是使用 TopCoder 的比赛形式， Topcoder 的算法竞赛有点类似于 IOI ，ACM-ICPC 之类的竞赛，题目是同
一个类型的。每次比赛三道题目，一般分数分配为 250-500-1000 ，比赛分为 Coding ， Rest ， Challenge和 System Test 四个
阶段，时间各是 75 分钟（现场比赛 85 分钟）， 5 分钟， 15 分钟（现场比赛 10 分钟）和不定。
TopCoder 的现场比赛都由 3 个阶段组成：所有选手被分为 3 个组（称为 Room1 ， 2 ， 3），每组分别进行半决赛，每组前 2(
或 3) 名直接晋级决赛， 3-6 名晋级 wildcard 比赛， wildcard 比赛 12 人中的前两名填补决赛的最后 2(或 1) 个名额，决赛
由 8( 或 10) 名选手参加。由于三大赛事的比赛形式相差不大，每次现场决赛的选手中总是有许许多多熟悉的面孔。
三大赛事的波荡起伏：
可能细心的同学能够发现疑问，在文章最开始的一段中，我表明自己在 2007 年之后没有错过任何现场赛事，那为什么没有GCJ2007
呢？其实原因很简单， Google 公司在 2007 年全年中只举办了面向美洲的比赛，没有举行面向全世界的公开赛。 GCJ2007的搁浅
也使得整个 2007 年只有 TopCoder 公司独自举办世界大赛。
但是，当大家以为 GCJ 将在记忆中淡去的时候， GCJ2008重新登陆，而且新的比赛环境与形式给选手以焕然一新的感觉。这里先谈
谈自己对这种新比赛环境的看法吧：
GCJ2006 仍然使用的是 TopCoder 标准形式，也就是说和 TCO 以及 TCCC 完全一样，用一句话概括就是Coding-250-500-1000-
Challenge-SystemTests 。
GCJ2008 比赛环境结合了 ACM ， TopCoder 还有 IPSC(ipsc.ksp.sk) 等多种比赛的特色。
(1) 每道题目分为 Easy-Hard 两组数据，并且数据可以下载到本地，这点好像与 IPSC 很相似，另一个与 IPSC的共同点就是，不
限制选手使用的编程工具，包括肉眼观察或者人工搜索。
(2)Easy 数据则和 ACM 非常近似，即时提交评测，并且也设定了每次失败提交加 4 分钟的罚时。
(3)Hard 数据则更像 TopCoder 的形式了， Hard 数据由于是统一评测， System Tests可以有效
地把悬念保留到最后一刻。
GCJ2008 的比赛形式是一种大胆的尝试，并且也已经有了很理想的结果。
另外，值得称赞的是， GCJ2008 中首次使用了分各大洲进行当地现场半决赛的赛制。使得排在前 500名的选手得以参加各大洲的半
决赛，也拉近了 Google公司与选手之间的距离。从另一个角度来说，各大洲半决赛的方法很有效保证了决赛选手的水平。平心而论
， TopCoder 现场比赛前的最后一轮网络淘汰赛对选手的压力很大，就连 Petr 在 2007 年都直接来了一个 “ 滑铁卢 ”，连现场
赛都没有进。而现场比赛的公平程度远超过网络赛，所以通过现场赛决定决赛选手可以一定程度上提高决赛选手的水平，至少我个人
很赞同这种做法。
搁浅的比赛无独有偶，可能是受到了 2008 年全球经济危机的影响， TCCC2008 也停办了。而且我们都觉得， TCCC2007很可能是
TopCoder 举行的最后一次 TCCC 了，当然 TopCoder 这样做没有不合理的地方。
TCO 则相对稳定一些，就连每年举行的地点都不变， TCO 连续 3 年在著名的赌城 Las Vegas举行。今年应该也不会改变地点。
三大赛事的举办，我觉得选手最大的受益就是，比赛提供了一个到美国免费游玩的机会。我先后去过 7 次美国，其中 6 次都是参加
编程比赛。通过比赛的机会，我们得以开阔眼界，结交朋友。我个人真心希望三大赛事能够继续举行，但是 2009 年秋天的 TCCC和
GCJ 很可能同时停办，这也是一个不可回避的问题，让我们拭目以待吧。
美国之旅：
从 2007 年以来的 4 次现场比赛，虽然每次比赛过程中都有一些遗憾，但是现在回想起来都有不尽的乐趣。
TCO2007 是我第一次到达赌城，一下飞机就看到很多赌场 (CASINO) ，可谁知 TCO2007整个比赛过程就是一场巨大的赌博。我当时
由于不熟悉 Texas Hold'em 的规则，在半决赛中搞错了 Flush 和 Straight的大小关系，结果初上赌场就倾家荡产而被淘汰出局。
TopCoder 比赛中竟然出赌博有关的题目，果然有 Las Vegas的特色呀。不过在赌场里，我仔细研究了许多赌博游戏的规则，然后写
了几个程序计算赌博的期望，但是发现标准概率模型下所有游戏的期望值全是负数（其实挺显然的），于是，也就以娱乐为目的和
lympanda 切磋了一下。
如果说 TCCC2006 的 Room1 是中国的胜利， TCO2007 的 Room1 则是中国的失败了，虽然 Ying 和lympanda 都进入了 wildcard
，可是都由于一些小失误输掉了这次赌博。赛后 lympanda 请我去牛排馆吃饭，后来那个牛排馆也成为每次 TCO比赛我们中国选手
的主要聚会地点。
TCCC2007 的小组赛还比较顺利，我轻松击败了 gawry ， Per ， marek.cygan获得小组第一挺进决赛。可是决赛中，我为了提高速
度以超过 Petr ，再加上有些紧张，最后 500 分和 1000 分两题又都挂了，落到了第 5 名。 TCCC2007地点设在了奥兰多，比赛结
束后我们到附近的 Disney Land去玩，那里的惊险游戏比国内刺激得多，有些远远超过我的极限，我们一行人一直玩到深夜才返回
。许多选手还一起到奥兰多魔术队主场观看了 NBA 现场比赛，可惜最后一节成为了垃圾时间。
TCO2008 我也依靠飘逸的 1000 分题中 800+ 分的提交闯入决赛。决赛前我还和 visualage聊天，夸耀自己从来没有所有题目全挂
，更没有拿过负分。可是在随后的决赛中，这两个 “ 梦想 ” 就都实现了， PE 对我的评价是太紧张了。基本每次 TopCoder现场
比赛都能见到 PE ，谁知他每次怀疑我某些题目的正确性的时候，我的程序就一定是错的，如果下次我参加决赛，您就不要再看我程
序了吧（呵呵，开个玩笑）。
不过在决赛 Challenge 阶段的最后时刻，我从第一视角目睹了 Petr 和 Tomek 的巅峰对决。在还有 15 秒钟结束时Petr 还落后
Tomek 大概 30 分左右， Petr 成功 Challenge 了一个超过了 Tomek ，但是 Tomek 利用短短的 10秒钟也提交了一个成功
Challenge 又超了回来，谁知 Petr 得到这个信息之后又提交了一个 Challenge ，可是运气稍差，如果那个数据用来Challenge 我
的程序的话， Petr 就能够在最后 1秒再次夺回冠军的位置。能够到最后一秒还能有机会成功翻盘的一定是神一般的人物，能够把
神一般的人物逼到最后一秒的也一定是神一般的人物，两个神一般的人物你来我往，为大家上演了一场精彩的比赛。
欧洲独霸：
又一次引用黄金雄教授在杭州 2008 时说的话， ACM总决赛的实力分布由原先的美洲独霸逐渐转向了现在的亚欧争霸。但是，我根
据这些年的比赛结果发现，从 2006 年开始，团体比赛和个人比赛，特别是个人比赛，欧洲选手一直保持着绝对的霸主地位，亚欧争
霸的说法实在有些牵强。
从 2005 年开始，几乎所有三大赛事的冠军都是欧洲选手。成绩最好的要数俄罗斯，俄罗斯选手以 Petr ， andrewzta等为代表。
俄罗斯选手训练刻苦，编程能力极强。欧洲的另一霸主就是波兰，波兰选手具有很强的灵气，以 tomek ， marek 以及 Eryx为代表
，程序设计在他们手中体现出了艺术气息。
前几天我也看到关于取消 NOIP 保送 资格的文章，我没有发表评论，因为我没有看懂，为什么文章里把保送和保送资格混为一谈，
让人觉得哭笑不得。这里我对 保送 资格还是想法不多，不过想比较一下我们中国选手与欧洲选手思维能力上的差别。
在高中时，吴文虎老师就常说中国选手的 IOI 成绩很优秀，的确这几年从 IOI 成绩上看，中国是绝对的霸主。可是 ACM-ICPC的成
绩，俄罗斯和波兰等强队的成绩却远在中国之上。于是我们总结的原因是：欧洲选手的编程能力强。我非常同意这个说法。
但是 “ 欧洲选手的编程能力强 ” 的说法并不说明他们的算法能力弱，相反他们的思维素质非常高，他们具有非常正统和严密的思
维方式，体现出经过长期训练的思维能力和素质。
我觉得中国的 “ 高手 ” 和许多通过高考进入名校的 “ 神人 ”，在大学之前接受的教育都是以选拔为目的的，并没有太多针对
思维方式和能力的训练。记得小学要考重点初中，初中则拼搏重点高中，高中期间则梦想名牌大学，而在学习期间，我们并没有太多
机会训练自己的思维能力，至少在我的中学阶段是这样的。虽然很多高中已经竭尽全力通过类似研究性学习的方法锻炼我们的创新能
力，但是仍然不能改变选拔性考试 “ 高考 ” 这一事实。而在与西方选手交流的过程中，我觉得许多思维能力优秀的学生很早就有
机会接受系统的思维能力训练，寻找最适合自己的思考方法。我一次有机会看 Eryx 留下的草稿，发现他考虑问题有非常严密的过程
，从理解题目到想出算法每步都有根有据，并不是随机碰撞的结果。
现在欧洲选手与我们相比，思维能力上也并没有劣势。我有幸在投身 OI 竞赛之后，得到许多机会与其它选手交流，学习他们的思考
方法，努力锻炼自己这方面的能力，试图与众多欧洲选手对抗。
Mountain View 登顶：
GCJ2008 在 Google 总部 Mountain View 举行，赛前我想用 Ying 的一句话来表达我对比赛夺冠的渴望， “我虽然获过很多奖，
但是缺少一个世界冠军 ” 。早在 GCJ2006 ，我就拥有机会获得冠军，但是在失去那次机会之后一等就是整整的两年。
比赛开始不久， bmerry 的强势起跑使我逐渐失去了夺冠的念头，只得一心做好眼前的题目。 bmerry 在不到 2个小时的时间里就
做出了除了 C- Hard 以外的所有题目，他只要在最后一小时做出 C- Hard ，就基本上可以锁定冠军了。
不过我克服开场的不顺利之后，磕磕碰碰地在 2 小时过 5 分顺利通过了 E-Easy 和 E-Hard 。摆在我面前的只有B-Hard 和 C-
Hard 。 B 题和 C 题相比之下， B 题我已经有了一定的想法，可是 C 则是完全没有想法。于是我决定先做 B ，GCJ2008 的 B 题
简直是我的克星，我先后用了 100 分钟时间做这题都没有结果，可以说当时状态很差。大概到了 2:40 的时候，我查看 board时突
然发现了一件令人窒息的事情， bmerry 已经尝试了 C-Hard 并且超时了。由于 C-Hard 的分数略高于 B-Hard，我最后想要超过
bmerry 就必须做出 C-Hard 。果断放弃 B-Hard 之后，并没有想出 C-Hard的方法，写了一个搜索程序但是心里很没底， Hard 数
据的提交时限是 8 分钟，于是到了 2 小时 52 分的时候，我毅然打开 C-Hard ，用搜索的程序运行 C-Hard，在焦急的等待之后，
程序在运行了 1 分多钟以后神奇地运行结束了。我依靠搜索方法通过了 C-Hard ，一举超过了 bmerry 。 1 分钟后zhuzeyuan 也
做出了同样的题目，超过了 bmerry ，由于罚时排在第 2 名。我和 zhuzeyuan 还有 bmerry比赛过程中都有不小的失误，我很有幸
把失误的损失降到了最低点，终于获得了第一个世界比赛的冠军。
这次 GCJ 的题目有非常详细的解答，可以在比赛的链接里找到。 GCJ2008的比赛结果从一定意义上，打破了欧洲选手多年的独霸场
面。加上原籍南非的 bmerry ，前五名中都没有出现欧洲选手的名字，这也是在多年现场比赛中没有出现过的。
这一年，我很高兴看到 OI 选手中出现了 ahyangyi ， yuhch123 ， Loner等各方面都极为出色的新人，真心希望你们能够早日适
应大学的学习生活，再创佳绩。
