BYR Achieve · 镜像论坛

ACM/ICPC By noodleman ACM/ICPC的背景介绍 ACM/ICPC(以下简称ACM竞赛)是国际大学生程序设计竞赛(International Collegiate Programming Contest)的简称，由美国计算机协会(ACM, Association for Computer Machinery)主办，旨在展示大学生创新能力、团队精神和在压力下分析并通过编写程序解决问题的能力。从1977年开始，ACM竞赛已经举办了33届世界总决赛，并演变为世界上规模最大、水平最高的大学生程序设计竞赛。比赛以团队的形式代表各学校参赛，每支队伍均由3名队员组成。参赛队员必须是高中毕业后5年之内的在校大学生，即从大一到研一的学生都具有参赛资格，但是每名队员最多只能参加2次世界总决赛。比赛期间，各参赛队伍只能使用1台电脑在5个小时内使用C、C++或Java中的任一种语言编写程序来解决6至10个问题。程序完成之后提交裁判运行，运行的结果会判定为正确或错误两种并及时通知参赛队。有趣的是，每队在正确完成一题后，组织者将在其位置边升起一只代表该题颜色的气球，以此来调动比赛现场的竞技气氛。每年度的ACM竞赛均由各大洲区域预赛和全球总决赛两个阶段组成。在各预选赛区报名和参赛人数的基础上，主办方根据特定的积分计算方法来最终决定每个预选赛区获得参加世界总决赛资格的队伍。平均情况下，每个赛区会有1~2支队伍获得出线资格。然而，国内的某些预选赛区由于其参赛学校和队伍众多而造成前5名的队伍均能出线的情况也是不足为奇的。不过，需要注意的是，每年参加世界总决赛的队伍个数是有限的，这几年都是100支队伍，同时赛事大会还规定每个学校最多只能派出1支队伍参加当年的世界总决赛，从一定程度上增加了比赛的竞技性和淘汰性。北邮自2002年开始参加ACM赛事，经过教练房鸣老师和历届北邮acmers的努力和拼搏，已经多次获得了预选赛区的各类奖牌，并且分别于2007年长春赛区和2008年北京赛区获得金奖，连续两次晋级ACM世界总决赛(2008年加拿大班芙和2009年瑞典斯德哥尔摩)！如何准备？首先，笔者想提醒一点，ACM竞赛是一项准备周期较长，比赛难度大，获奖期望不那么高但是收益却相对丰厚的比赛。如果你真心热爱它并且想踏踏实实地做出一番成绩来的话，或者是想让它成为你申请出国的筹码的话，请持之以恒地训练下去，那么最后的胜利将离你不远；否则，如果你一直处于慢慢地尝试或者是随意玩玩的状态，我建议你及早退出的好，或许还可以把宝贵的时间用在其他有价值的事情上。从ACM竞赛(国际大学生程序设计竞赛)的字面上来看，你可能会认为它仅仅是关于编程的竞赛。事实上，它考察的更多的是算法(特别是计算机算法)和数学方面的比拼。粗略地讲，ACM竞赛可能会考察的算法大概可以分为排序和顺序统计、递归和分治、贪心法、动态规划、搜索和剪枝技术、初等数论、组合数学、图论(含网络流)、计算几何以及数据结构相关的专题。由于算法范围的广泛性和复杂性，不可能把所有的专题都了解并精通，所以对刚刚起步的新手来说，切忌急躁和贪多，最好从某几个感兴趣的专题入手，由简入深才是正道。结合各前辈和笔者的经验，我认为在准备竞赛的过程里主要需要做两件事：看论文、书等资料学习算法，然后上在线评测网站(online judge，北邮的OJ地址为：)做编程练习。整个训练可以分为4个阶段：入门阶段，学习基本的数据结构和简单算法，同时开始在评测网站上做题，以简单题为主，主要训练自己的把算法转变为代码的能力；初级阶段，经过一定的入门，便可以开始找寻自己感兴趣的且相对擅长的专题进行集中训练，在较深入地学习其原理和方法的同时也增加做题的难度；中级阶段，当有了大约300~400道题目的积累后，你可能需要训练自己融合不同算法专题的能力，仔细研读一些专业资料并有意地挑选一些相关的、有难度的题来练习；高级阶段，此时你大概已经有了600道甚至更多的题目积累，对某几个算法专题也有了深刻的理解，那么扩大自己的算法知识面和在数学上加强自身的修养是个不错的选择。关于具体的参考书籍和解题技巧等问题，可以到北邮人论坛的算法与程序设计竞赛板块进行讨论(http://forum.byr.edu.cn/wForum/board.php?name=ACM_ICPC)。最后，需要指出的是，在训练的任何时候，把问题拿出来向别人求教或是与他人讨论永远是最高效的学习方法。因为ACM竞赛难度大，笔者强烈建议同学们最好在大一的时候就开始准备它，毕竟很多算法知识的灵活运用需要长期的理解和积累，是不能一蹴而就的，而且大一相对小的课业压力方便腾出富裕的时间来集中练习。如何代表学校参赛？一般情况下，同学们需要自己组队(人数<=3即可)报名参加当年的北邮程序设计大赛，并通过网络预选赛进入到现场决赛。现场赛的前5名队伍的所有队员(大约15个名额)可自愿成为校队队员，如果有人放弃导致名额未满则按名次往后顺延给下一队伍的成员。事实上，这只是新队员的初选，即使你在现场赛没有获得资格也有可能最终代表学校参加区域预选赛，因为所有同学不论是否为校队成员都可以到主楼912、915实验室来训练或参加讲座培训，而且整个训练过程是公开积分制的。也就说，经过当年的暑假集训后，最终选拔成绩最好的一部分同学(不限于校队成员，大约15~18名)组队参加本年度的区域预选赛，故归根结底还是看同学们自身的实力。关于具体的参赛准备和训练安排等事宜，请到北邮人论坛的算法与程序竞赛版块查看。 ACM竞赛和留学申请在北邮，相当一部分的ACM队员会选择毕业后去hunting for good jobs，只有一小部分队员尝试申请出国留学这条路。笔者有幸先后接受了ACM竞赛和出国申请的洗礼，对于ACM竞赛在留学申请中所起的作用算是略有所悟，下面就结合笔者的个人经历进行介绍。在申请的所有影响因素里，除去GPA和各类英语成绩等必要条件外，一份丰富的、有价值的研究经历(成果)或许是最有分量的因素了。准备和参加ACM竞赛本身就可以被看作是一种研究经历，申请者完全可以在ps里阐述自己在这方面的工作，比如学习过哪些算法，阅读过哪些书籍，用改进过的数据结构和算法解决了一个特定的问题等等。所有的这些都是在向教授传递一个讯息，你通过ACM竞赛的的确确在数学、算法和编程方面进行过较为深入的理解和积累，从而让教授觉得你是个不错候选者。再者，如果你在ACM竞赛中获得了好的名次，加上在竞赛中积累的能力，你会比别人更容易地获得各大IT公司，特别是一些企业(比如Microsoft、IBM)的研究机构的实习机会。凭借在这些机构的实习经验，既可以在简历中添上一笔不错的经历，还可以帮助你丰富ps里的研究素材，增强其学术性，更重要的是，当你准备陶瓷或者教授的面试时再也不会因为研究经历少而发愁了，而可以滔滔不绝地介绍你在实习中做的研究项目，进而增加被录取的机会。举一个本人的例子，笔者曾凭借自身的实力和ACM竞赛不错的名次先后获得了百度和微软亚洲研究院的实习，积攒了较为丰富的研究经历，也为本人的申请奠定了坚实的基础。虽然笔者给不出一个准确的、定量的值来描述ACM竞赛在申请中的有用程度到底有多大，但是笔者可以负责任地说，ACM竞赛在国外大学教授眼里绝对是受认可的而且能对申请起到非常积极的作用。在笔者和一名UIUC的CS教授的联系中，该教授明确地表示，ACM竞赛的reputation很好，如果能进入世界总决赛的话是非常了不起的。其实，在浏览北美各大牛校的EECS系的网站后，你会发现里面不乏参加过ACM竞赛甚至是世界总决赛并取得好名次的学生，于此关于ACM竞赛的有用、认可度应该是可见一斑了。最后，笔者想指出的是，不论ACM竞赛的含金量有多么高，认可度有多大，即使你在世界总决赛中获得了不错的名次，也并不能保证你在留学申请里就一定会成功，当然，不光是ACM竞赛，其他任何一项竞赛也没法做出这样的保证。笔者认为，在研究兴趣和方向match的情况下，教授们最看重的还是申请者的学校和GPA，然后再是研究经历(成果)和竞赛等等，对于学科竞赛，他们认为那是应该在学有余力的情况下开展的。总的来说，在笔者眼里，一个优秀的申请者应该有一个高的GPA，同时在对申请方向有一定认识的情况下，在有关竞赛中取得了不错的成绩以及在研究结构做过该方向的科研项目，而且在ps、cv等文书创作上具备较高的水平。结语参加ACM竞赛和准备留学申请都是一条充满变数的道路，既需要参与者的互相帮助更需要前人的宝贵指引。我曾有幸在这两个过程中得到许多前辈和同学的帮助，至今仍心存感激，故写下本文以寄托对他们帮助的感谢，同时也希望文中关于ACM竞赛以及留学申请的信息能对后来者所有帮助和启发。

ACM竞赛简介 -- noodleman