|
本篇开始主要介绍国内大学生的算法方向的竞赛。 ACM国际大学生程序设计竞赛是最负盛名的大学生程序设计竞赛了，其全称为International Collegiate Programming Contest，简称ICPC，由Association for Computing Machinery（国际计算机学会）主办。国际计算机学会简称ACM，计算机科学领域的最高奖图灵奖就是由ACM评选出来的，而由ACM主办的ICPC自然保证了权威性和含金量。正因为如此，互联网的头部企业十分青睐在ACM/ICPC中表现优异的选手，而在ACM/ICPC中脱颖而出的选手，许多已经在学术界和产业界取得了巨大的成就。 事实上，ACM/ICPC是几乎所有顶尖OI选手到大学之后的自然选择，许多NOI集训队选手、IOI金牌在大学阶段也同时拿到了ACM/ICPC全球总决赛的金牌，比如教主楼天城、陈立杰、金策等。所以算法竞赛真的是可以从小学一直打到大学，也许除了数学竞赛可以做到之外，也没有任何一门学科竞赛可以如此具有延续性了。 历史渊源 令人意想不到的是，在程序设计发展的早期，上世界70年代，就有了程序设计竞赛——1970年在美国德克萨斯A&M大学举办了首届比赛，然后很快得到美国和加拿大各大学的积极响应。1977年，举办了首次总决赛，并演变成一年一届的国际性比赛。 赛事早期，由于参赛队伍的地域所致，冠军基本上是美国和加拿大的大学获得，1990年以后，开始有美国以外的国家夺冠，而进入21世纪，冠军基本上被俄罗斯垄断了。 至于我们中国，上海交通大学于2002年美国夏威夷，2005年中国上海，2010年中国哈尔滨三次获得全球总决赛冠军，浙江大学于2011年在美国奥兰多夺得全球总决赛冠军。有些出人意料地是，垄断了NOI集训队选手、学生整体水平最高的清华大学和北京大学，虽然金牌拿了不少，但是一次也没有获得过全球总决赛冠军，即使是楼天城、陈立杰、金策等人，也在ACM/ICPC总决赛上留下遗憾，其竞争之激烈可见一斑。 赛事体系 由各大洲区域赛（Regional）和全球总决赛（World Final）构成，区域赛一般是每年9-12月举行，全球总决赛则安排在次年3-5月，只有在区域赛中表现优异，才有资格入选全球总决赛。 比赛赛制 ACM/ICPC与OI虽然都是算法竞赛，考查的知识点和能力有很大程度上的重合，但是在赛制上有较大差别。 第一个差别是参赛队员。OI是个人赛，ACM/ICPC是团队赛。ACM/ICPC参赛队伍最多3人构成（理论上也可以1个人作为一支队伍，据说楼天城就干过这事，然后一个人吊打全场，楼教主的威名于是传播开来），一支队伍只提供一台电脑。所以ACM/ICPC相比OI，多了团队直接的配合，更接近真实的工作环境。 第二个差别是题量。NOI和IOI每场比赛都是5个小时3道题，ACM/ICPC则是5个小时7至13题不等，所以尽管是团队赛，但是题量的增加，还是非常考验选手的解题能力以及团队配合的默契。对了，ACM/ICPC是全英文题面，即使是国内的区域赛，也只提供英文题面，而IOI还可以由领队翻译为中文题面提供给选手。当然，优秀的算法竞赛选手，英语（至少阅读）都是不会差的。 第三个差别是评分机制。OI是按测试点评分，ACM/ICPC则是按通过题目数量和用时进行评分。在OI赛制下，一道题目如果无法写出规定时限内的正解，是可以根据数据范围特点写部分分的。ACM/ICPC则要求一道题必须通过所有测试点、得到Accpted，该题才算通过，否则就是WorngAnswer等其他反馈，没有部分分。ACM/ICPC这样的评分机制也有现实意义：登月程序必须完全正确，才能保证飞船进入正确的轨道，总不能允许一个几乎完全正确的程序，导致飞船最后偏离了些许轨道，最后飞向太阳系的其他地方吧。 当然，配合这样的评分要求，ACM/ICPC是有即时反馈的，一道题目提交以后，是否通过都会即时反馈，一道试题可以反复提交，只不过每一次错误的尝试，都会增加罚时。国内的OI比赛没有即时反馈的机制，选手必须自己评估所写程序的正确性，直到考试结束才会测评。在这一点上，ACM/ICPC又显得更为友好，也更为有趣，每通过一道试题，官方就会在该队伍的桌上挂上相应颜色的气球，显得非常好看。而在前4个小时里，可以看到全部队伍的实时排名，显得非常刺激；最后一个小时封榜，无法看到排名，留足了悬念；比赛结束后的最后滚榜，又是激动人心的时刻。 第四个差别，OI是闭卷考试，ACM/ICPC则是开卷考试，允许携带纸质参考资料。所以ACM/ICPC理论上是不需要背诵算法模板的，可以把更多的精力放在思维层面而不是记忆层面。但是优秀的队伍都会事先编写准备适合自己代码风格的模板，只有适合自己的码风用起来才顺手。 尽管ACM/ICPC与OI在赛制上有比较多的差异，但是毕竟都是算法竞赛，所以OI的顶尖选手，在ACM/ICPC上也是能很快适应的，只要解决配合的问题，其团队实力往往也是顶尖的。甚至每年一些OI强校（例如杭州学军中学）派出的中学生队伍参加ACM/ICPC区域赛，取得了金牌乃至全场冠军的优异成绩。 |
|
|
