《楼天城楼教主的acm心路历程作为励志用》由会员分享，可在线阅读，更多相关《楼天城楼教主的acm心路历程作为励志用（41页珍藏版）》请在金锄头文库上搜索。
1、利用假期空闲之时，将这几年GCJ，ACM，TopCoder 参加的一些重要比赛作个回顾。昨天是GCJ2006 的回忆，今天时间上更早一些吧，我现在还清晰记得3 年前，我刚刚参加ACM 时参加北京赛区2005 和杭州赛区2005 的情况。2005 年ACM-ICPC酸甜苦辣我进入清华大学开始本科学习的时间是2004 年8 月，在进入清华大学的第一年里，由于基础课学习比较紧张，再加上计算机系不允许大一学生自带电脑，我没有参加2004 年的ACM 比赛。不过在大一一年中没有停止这方面的练习，对ACM还是热情高涨。大概在2005 年7 月底，与同班同学shell（贝小辉）和superzn（张宁）一起决
2、定组队参加ACM 比赛。对于队名没有太多的想法，就随便取了一个字典序靠前一点的bomber。随后进行的几场训练中，我的编程状态一直保持得很好，训练比赛的主要方式都是：我主写程序，shell 和superzn 负责翻译题目，思考算法和测试。这种组队模式一直沿用到我们后面的所有比赛中。2005 年底，我们报名参加了2005 年的北京赛区和杭州赛区的比赛。顺利通过了预赛进入了现场决赛。记得当时北京赛区预赛的时候，我和superzn 一起在参加百度之星程序设计大赛，shell 依靠一人之力过了6 题，最后以第二名的资格参加北京赛区现场比赛。北京赛区：2005 年的北京赛区地点设在隔壁的北京大学，由于交
3、通非常方便，我们没有和大部分选手住在一起，不过也没有参加Java-Challenge 和晚上的表演。练习赛之前，说到比赛位置抽签，本身意义不是很大，可是邬老师神奇的RP把两只清华的队伍抽在一起，结果练习赛进行了一半，另一只清华的队伍THU1（队员是：吴景岳，栗师和金凯，好像后来队名改成了DreamCatcher，不是很确定）被要求换到一个比较远的地方，理由是有些学校觉得这样不合理。后来很多赛区也出现过队伍座位在一起的情况，邬老师的RP 果然不是盖的。记得练习赛时和复旦的LemonTree（盛城）一起在场地里闲逛，结果果然不到10 分钟就被要求回座位了。还有当时比赛场地是一个体育馆，有些队伍把气
4、球放飞之后气球就飘在天花板下了，总裁判李文新老师还威胁我们说，如果明天正式比赛把气球放飞，就不算通过相应的题目，除非有办法把气球取下来。然后就是比赛的过程了，下面有底纹的文字是我找到的当时留下的比赛总结：E：快速排序。5 分钟1Y。我想5 分钟的时间可以争取这几年ACM 国内赛区的最快出题记录了吧。G：二分答案+最小生成树。25 分钟1Y。这题就是经典的最优比例生成树问题，我们一致认为这题比较简单。不过后来被李文新老师批评了，说法是误导其他的队伍。不过说到最优比例生成树问题，TCO2006 的时候fwj 和tomek 竟然都没有见过这道题目，这题可是源于POI 呀。我想我们认为这道题目简单的主
5、要原因是我们都在冬令营上见过这到题目，如果第一次看见，想出算法可能确实需要一些时间。在这里向被我们影响的队伍的道歉，最终G 提交了200 多次，但是只有8 个队伍AC。C：二分图最大匹配。42 分钟1Y题目要求计算一张图的最小覆盖集，可能唯一的tricky 是发现图是二分图。D：遇到了一定的困难，发现A 很简单，于是先放一下D 是一道比较综合的题目，设计一些简单的计算几何和字符串处理的知识。A：简单的几何问题，出现了一个低级错误，提交了3 次均为WA。A 是北京赛区最简单的题目，我的程序里犯了一个很低级的错误，可能也是经验不足造成的吧。D：重新写，但是没有考虑一种情况，WA 了1 次。87 分
6、钟，复旦的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 的领先，当时心情很激动，不过由于缺少经验，也影
7、响了接下来的发挥。其实，现在回想起来，这次比赛其实是一个很好的AK 的机会。F：DP。程序比较复杂，WA 了4 次。F 是一道比较复杂的动态规划的题目，其实WA 的原因是一个应该用int64 的地方，我们使用了int，这个地方的确很难发现。H：F 一时无法AC，只好转功H。H 就是普通的模拟题。开始没有考虑坦克和炮弹可能在1/3 秒相遇，WA 了1 次。比赛还有一个小时，封板。H：shell 发现了坦克和炮弹可能在1/3 秒相遇的情况，250 分钟左右AC。对于我们这种组队模式，当主写程序的选手状态不好的时候，很容易出现连续卡题的情况，这种情况的出现很不利于水平的正常发挥。在北京赛区的比赛中，
8、我们很有幸没有出现连续卡处的情况。记得，当时北京赛区的Judge 的半自动的，就是说如果结果是AC，速度就会非常快，否则由于人的介入，不能AC 的提交往往需要等一段时间。我们第2 次提交H 之后，没有得到很快的回复，以为已经WA 了，于是我和superzn 继续测试一些数据。但此时，突然有一个mm 从左边走过来插气球，这个气球也成为了全场唯一的蓝色气球，这个意外之喜最后成就了第一个分区赛冠军。F：下面就是痛苦地提交F，一直战斗到最后一刻，WA 了14 次，留下了北京赛区最大的遗憾。在最后时刻我们似乎发现了那个int64 的错误，不过当时思路已经比较混乱了，没能改对。F 的问题也导致没有时间写I
9、，当时如果直接重写后者换superzn 来写F，完全可以在比赛结束前AC。比赛的大致过程如上所述，那个神奇的气球，我现在仍然记忆犹新。最终有4个队伍攻破7 题，Abacus 的组成应该是盛城，timegreen 和suzhan 吧，Eccentric 中我只记得辛韬，ZSU_Panku 中我记得Savior（陈实）。上述的老朋友之后见面的机会就很少了，分区比赛也成为了我好需要老同学重要的交流机会了。我ACRush 的ID 估计就是那时开始使用的吧，转眼就已经3 年多了。比赛前后还记得经常与复旦大学的吴永辉老师聊天，在那之后的每次比赛我都能见到他年轻的身影。现在回想起北京的分区赛，很有幸能够在第
10、一次参加ACM 正式比赛就获得分区比赛的冠军。我想是由于现场气氛对许多队伍都有不小的影响吧，当时许多队伍都卡在几道比较繁琐的题目上了，题目的算法性都不是很强。我大概从那时才刚刚接触TopCoder，如果能够早一些，相信会更适应这样的比赛。杭州赛区：2005 年的ACM 杭州赛区比赛在浙江大学举行，杭州赛区的时间就在北京赛区结束后一周，最初选择杭州赛区的原因很飘逸：我自己家在杭州。实际上也差不多，我随队伍（当时THU 派了3 只队伍参加杭州赛区的比赛，除了我们队之外，b142857（侯启明），zhy（周源），ysy（杨 思雨）组队，另外一只由汪汀，王俊和黄源河组成）一同抵达杭州车站之后就马上回家
11、休息了，直到比赛前才赶回。在北京到杭州赛区之间的一周中，我的状态就在 不断下滑，在家中完全失去了比赛的气氛，回到赛场再也找不到感觉了。一场悲剧即将上演。我们先看看比赛过程吧，下面有底纹的文字是我找到的当时留下的比赛 总结：G：初看很简单，但是调试了30 分钟没有结果。G 是一道数学问题，其实具体数学书上有明确的公式，不过我们使用的递推方法应该也可以得到正确的结果。程序中犯了一些低级的错误，由于实在不在状态，调试了30 分钟还没有找到错误。这里还暴露了一个组队模式的问题，在后来的组队模式中，如果像这样没有想清楚算法的题目队友是一定不允许我去写的。A：模拟。41 分钟AC，当时肯定没有想到这是唯一
12、一道1Y 的题目。A 是一道模拟题，1Y 的时候已经很晚了，排名也很靠后。C：图论。但是由于堆栈逸出RTE 了5 次，浪费了大量的时间。C 的问题关于树中祖先关心的判定，题目很简单，实现的方法也很容易，就是通过一遍DFS 来计算。但是我们忽视了一个从来没有遇到过的问题：堆栈溢出。而且，堆栈在本地机器上运行过程中，Eclipse 提供了8MB 左右的堆栈，所以没有溢出，但是在提交之后的环境下运行就溢出了。而且每次RTE 之后，我们一直在尝试修改数组的大小，一直没有找到根本原因。调试C 的同时，我也尝试修改G，结果G 也错了8 次之多，并且始终都是WA。I：shell 在我郁闷地调试C 和G 中A
13、C 了，之前WA 了一次。I 是动态规划问题，WA 一次可能是忽视了一些边界情况。D：网络流，没有想到先贪心进行优化。TLE 了5 次最终没有通过。D 就是计算最小割，我们事先准备了先流推进算法，不过根据这道题目的模型，先流推进算法遇到最坏情况：二分图。由于当时dinic 还不是很流行，我们TLE 了5 次还没有通过。郁闷地调试D 和G。E,B：都尝试过，但是都出现了不明的问题。在随后的时间里，不断调试D 和G，但是始终不能AC。之后又尝试E 和B，E通过分段的方法可以处理，B 是数学题目。正常的话E 和B 并不是很困难的题目，但是当时已经非常混乱，连样例都没有通过。最终我们只过了3 题，排在
14、21 名，经历了我参加ACM 以来最惨痛的失败。这次失败主要归过与我状态太差，基本上什么题目都不能顺利通过。当然题目的选择也有很大的问题：G 确实不是难题，但是由于未知的原因始终不能通过，后来我把纸上的程序敲在ZJU 上就AC 了，至于现场为什么不能AC 我现在还是不能明白。如果说第一题的选择直接影响了我们的信心，那么D 的堆栈溢出则完全打乱了我们的节奏。对于我们的组队模式，卡出2 题已经超出了极限，我们不可能再尝试其他题目。Abacus 也来到了杭州，他们前期体现了强劲的先期优势，在2 小时就达到了6题；b142857（侯启明），zhy（周源），ysy（杨思雨）的队伍表现得相当神勇，在最后一小时超越了Abacus，夺得了冠军
