遥想小魔王的计算机竞赛峥嵘岁月

利用假期空闲之时,将这几年 GCJ,ACM,TopCoder 参加的一些重要比赛作个 回顾。昨天是 GCJ2006 的回忆,今天时间上更早一些吧,我现在还清晰记得 3 年前,我刚刚参加 ACM 时参加北京赛区2005和杭州赛区2005的情况。

2005 年 ACM-ICPC——酸甜苦辣

我进入清华大学开始本科学习的时间是 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。129 分钟 AC。

B 是一道明显的 2SAT 问题,由于题目比较长,我们没有很早发现这道简单题。 D:发现了 D 的没有考虑的情况,140 分钟 AC。

看了一个 board,那时 Abuacus,Eccentric 都只有 4 题,能够在第一次参加正 式比赛就做到 6-4 的领先,当时心情很激动,不过由于缺少经验,也影响了接下来 的发挥。其实,现在回想起来,这次比赛其实是一个很好的 AK 的机会。

F:DP。程序比较复杂,WA 了 4 次。

F 是一道比较复杂的动态规划的题目,其实 WA 的原因是一个应该用 int64 的地方,我们使用了 int,这个地方的确很难发现。

对于我们这种组队模式,当主写程序的选手状态不好的时候,很容易出现连续卡题的情况,这种情况的出现很不利于水平的正常发挥。在北京赛区的比赛中,我 们很有幸没有出现连续卡处的情况。

记得,当时北京赛区的 Judge 的半自动的,就是说如果结果是 AC,速度就会非常快,否则由于人的介入,不能 AC 的提交往往需要等一段时间。我们第 2 次提交 H 之后,没有得到很快的回复,以为已经 WA 了,于是我和 superzn 继续测试一些 数据。但此时,突然有一个 mm 从左边走过来插气球,这个气球也成为了全场唯 一的蓝色气球,这个意外之喜最后成就了第一个分区赛冠军。

在最后时刻我们似乎发现了那个int64的错误,不过当时思路已经比较混乱了, 没能改对。F的问题也导致没有时间写 I,当时如果直接重写后者换 superzn 来写 F, 完全可以在比赛结束前 AC。

比赛的大致过程如上所述,那个神奇的气球,我现在仍然记忆犹新。最终有 4 个队伍攻破 7 题,Abacus 的组成应该是盛城,timegreen 和 suzhan 吧,Eccentric中我只记得辛韬,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。

:shell 在我郁闷地调试 C 和 G 中 AC 了,之前 WA 了一次。

I 是动态规划问题,WA 一次可能是忽视了一些边界情况。 D:网络流,没有想到先贪心进行优化。TLE 了 5 次最终没有通过。

D 就是计算最小割,我们事先准备了先流推进算法,不过根据这道题目的模型, 先流推进算法遇到最坏情况:二分图。由于当时 dinic 还不是很流行,我们 TLE 了5 次还没有通过。

郁闷地调试D和G。在随后的时间里,不断调试 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 竞赛可以看作一些老朋友一起进行的一场智力游戏。