人大ACM队参加第38届ACM-ICPC世界总决赛

2014年6月22日-25日，第38届ACM国际大学生程序设计竞赛世界总决赛（ACM-ICPC World Finals）在俄罗斯叶卡捷琳堡举行，由信息学院朱青老师指导并带队、学生汪道鹏（2011级）、苏蕉（2011级）、王瀚达（2012级）亚洲金牌队组成的我校代表队与来自世界各地一流高校的122支队伍同场竞技，最终荣获第34名（官方排名并列第19名）。此次参赛是继2005年、2006年与2013年之后，我校ACM队又一次冲出亚洲参加世界总决赛。

第38届ACM国际大学生程序设计竞赛世界总决赛由IBM赞助、俄罗斯乌拉尔联邦大学(Ural Federal University)承办，选手经过2013年9月～12月各大洲预赛，共有来自6大洲、94个国家或地区的2286所学校参赛，最终有122所学校获得了参加全球总决赛的资格。

中国代表队经过2013年下半年的亚洲区预选赛有16个学校获得全球总决赛的资格，其中包括：北京大学、清华大学、中国人民大学、上海交通大学、浙江大学、复旦大学、中山大学、北京理工大学、香港中文大学、台湾大学等国内知名大学。

图1：人大ACM代表队全体老师与队员

人大ACM队于6月22日到达俄罗斯叶卡捷琳堡，随后在志愿者的陪同下住进了酒店，并于晚上完成了注册。全队进入了紧张的竞赛准备阶段。赛事的主办方是乌拉尔联邦大学。赛场设在叶卡捷林堡著名的滴血大教堂旁边的KOCMOC赛场，赛场布置了严格的安检，赛场中全世界各参赛队大学标记明显标出，我们Renmin University of China是第57队（Team 57），赛事安排依照每年的惯例严格按照美国ACM协会的ACM-ICPC组委会的要求进行。

Schedule网址：http://icpc.baylor.edu/worldfinals/schedule

6月24日，各个队伍参加了热身赛。热身赛的题目一共10道，我们的队伍在热身赛当中发挥非常稳定，进一步熟悉系统环境、解出了所有题目，最终排名大概是十几名，这也让我们的队伍对于第二天的正式赛充满了信心。

6月25日上午，各个队伍在音乐的伴奏声中依次进入比赛场地，通过观察场内悬挂的不同气球颜色可知一共有12道题目，入座之后主办方开始宣读比赛规则以及注意事项。上午10点，世界总决赛正赛开始。

图2：热身赛竞赛现场队员与教练

图3：第38届ACM-ICPC World Finals竞赛现场

比赛开始后的十几分钟之内各队伍一直处在读题和寻找简单题的状态之中，到了17分钟的时候，清华的队伍通过了全场第一个题目，K题。这道题目的阅读任务分配给王瀚达，王瀚达把题意告诉了另外两个队员，然后苏蕉略加思索之后，过了不久他便想出了做法，经过一段时间的编码和调试之后成功通过了这道题目。接下讨论D题，在苏蕉写K题的过程中，汪道鹏和王瀚达一直在对D题进行讨论，想出了一个复杂度比较高的解法，苏蕉写完D题后也加入了讨论，提出了一个复杂度较低的解法并且开始写D题，过了不久就通过了D题。

对于I题的求解不顺利，讲的是求一个平面上有若干个点（点数<=100），距离不大于某个长度的点对两两连边，求这个图的最大团。这个题目的数据范围对于一般情况的最大团算法在时间复杂度上难以承受，实际证明算法超时了，于是暂时性地放弃这道题。C题是一个计算几何+物理的题目，讲的是在一个放在地面上的多边形的一个点上悬挂重物，重物的重量应该在什么区间才能使多边形不失去平衡。这道题的解法就是通过力矩的关系建立以重量为未知数的不等式来解出来重物的重量区间，思路是很直白，但是细节比较多。苏蕉解法提出来并给出算法，然后由王瀚达进行编码，由于代码反复提交修补过多，这份代码越来越难以找出bug，决定由苏蕉来重写这道题目，提交便直接通过了这道题目。最终，我们队伍以通过三题的成绩加耗时名列第34名。

官方排名并列第19名，解出3道题目（同题目按照字母顺序排列）。

网址：http://icpc.baylor.edu/worldfinals/results

我校ACM队继去年获得世界总决赛资格后再次进军世界总决赛，积累了宝贵的经验，期待ACM队再接再厉，创造更优异的成绩。人大ACM队带队的教练朱青老师，这次同行老师有杜忠朝老师和孙辉老师。

为了激励参赛队伍获得好成绩，ICPC执行主席Willian Bill Poucher与人大队员合影，希望并鼓励ACM队员努力拼搏取得好成绩。队员们跃跃欲试为参加2015年举行的第39届ACM-ICPC世界总决赛继续努力。希望明年能够再次来到世界总决赛的赛场并且取得更好的成绩。

图4：ICPC执行主席Willian Bill Poucher与人大队员合影

附：

ACM-ICPC官网网址：http://icpc.baylor.edu/

第38届ACM国际大学生程序设计竞赛世界总决赛（ACM-ICPC World Finals）由俄罗斯乌拉尔联邦大学主办，IBM赞助，于2014年6月22日-26日在俄罗斯叶卡捷琳堡顺利举行，来自世界各地的122所高校同场竞技。

第38届ACM-ICPC世界总决赛经过上百场区域赛的选拔，共有来自世界各地的122支高校代表队晋级本次ACM-ICPC全球总决赛，参赛队伍中有麻省理工学院、斯坦福大学、卡内基梅隆大学等世界顶级大学。

2014年ACM-ICPC世界总决赛冠军是俄罗斯的圣彼得堡大学（St. Petersburg State University）；亚军俄罗斯的莫斯科大学（Moscow State University）；季军是中国的北京大学（Peking University）。此次参赛是继2005年、2006年与2013年之后，我校ACM队第四次参加世界总决赛。

经过近30多年的发展，ACM国际大学生程序设计竞赛已经发展成为最具影响力的大学生计算机竞赛。ACM国际大学生程序设计竞赛(英文全称：ACM International Collegiate Programming Contest（ACM-ICPC或ICPC）是由美国计算机协会（ACM）主办的，一项旨在展示大学生创新能力、团队精神和在压力下编写程序、分析和解决问题能力的年度竞赛。

ACM-ICPC以团队的形式代表各学校参赛，每队由3名队员组成。比赛期间，每队使用1台电脑需要在5个小时内使用C、C++、Pascal或Java中的一种编写程序解决7到12个问题。程序完成之后提交裁判运行，实时提交、实时评测，运行的结果会判定为正确或错误两种并及时通知参赛队。最后的获胜者为正确解答题目最多且总用时最少的队伍。与其它计算机程序竞赛相比，ACM-ICPC的特点在于其题量大，每队需要5小时内完成8道题目，甚至更多。另外一支队伍3名队员却只有1台电脑，使得时间显得更为紧张。因此除了扎实的专业水平，编程技术、良好的团队协作和心理素质同样是获胜的关键。