ACM竞赛之新人向导 ACM竞赛之新人向导 我们学校的计算机学院从去年起开始组织学生参加世界上最具权威性的大学生程序设计竞赛——ACM/ICPC。从这学期开始,学院计划有组织地进行训练和讲座,以帮助大家在有限的时间内尽可能多地提高自己的能力,这对有兴趣投入数据结构与算法研究的同学来说无疑是一件好事。但是,刚刚接触信息学领域的同学往往存在很多困惑,不知道从何入手学习,在这篇文章里,我希望能将自己不多的经验与大家分享,希望对各位有所帮助。 一、语言是最重要的基本功 无论侧重于什么方面,只要是通过计算机程序去最终实现的竞赛,语言都是大家要过的第一道关。亚洲赛区的比赛支持的语言包括C/C++与JAVA。笔者首先说说JAVA,众所周知,作为面向对象的王牌语言,JAVA在大型
的组织与安全性方面有着自己独特的优势,但是对于信息学比赛的具体场合,JAVA则显得不那么合适,它对于输入输出流的操作相比于C++要繁杂很多,更为重要的是JAVA程序的运行速度要比C++慢10倍以上,而竞赛中对于JAVA程序的运行时限却往往得不到同等比例的放宽,这无疑对算法设计提出了更高的要求,是相当不利的。其实,笔者并不主张大家在这种场合过多地运用面向对象的程序设计思维,因为对于小程序来说这不旦需要花费更多的时间去编写代码,也会降低程序的执行效率。 接着说C和C++。许多现在参加讲座的同学还在上大一,C的基础知识刚刚学完,还没有接触过C++,其实在赛场上使用纯C的选手还是大有人在的,它们主要是看重了纯C在效率上的优势,所以这部分同学如果时间有限,并不需要急着去学习新的语言,只要提高了自己在算法设计上的造诣,纯C一样能发挥巨大的威力。 而C++相对于C,在输入输出流上的封装大大方便了我们的操作,同时降低了出错的可能性,并且能够很好地实现标准流与文件流的切换,方便了调试的工作。如果有些同学比较在意这点,可以尝试C和C++的混编,毕竟仅仅学习C++的流操作还是不花什么时间的。 C++的另一个支持来源于标准模版库(STL),库中提供的对于基本数据结构的统一接口操作和基本算法的实现可以缩减我们编写代码的长度,这可以节省一些时间。但是,与此相对的,使用STL要在效率上做出一些牺牲,对于输入规模很大的题目,有时候必须放弃STL,这意味着我们不能存在“有了STL就可以不去管基本算法的实现”的想法;另外,熟练和恰当地使用STL必须经过一定时间的积累,准确地了解各种操作的时间复杂度,切忌对STL中不熟悉的部分滥用,因为这其中蕴涵着许多初学者不易发现的陷阱。 通过以上的
,我们可以看出仅就信息学竞赛而言,对语言的掌握并不要求十分全面,但是对于经常用到的部分,必须十分熟练,不允许有半点不清楚的地方,下面我举个真实的例子来说明这个道理——即使是一点很细微的语言障碍,都有可能酿成错误: 在去年清华的赛区上,有一个队在做F题的时候使用了cout和printf的混合输出,由于一个带缓冲一个不带,所以输出一长就混乱了。只是因为当时judge team中负责F题的人眼睛尖,看出答案没错只是顺序不对(答案有一页多,是所有题目中最长的一个输出),又看了看程序发现只是输出问题就给了个Presentation error(格式错)。如果审题的人不是这样而是直接给一个 Wrong Answer,相信这个队是很难查到自己错在什么地方的。 现在我们转入第二个方面的讨论,基础学科知识的积累。 二、以数学为主的基础知识十分重要 虽然被定性为程序设计竞赛,但是参赛选手所遇到的问题更多的是没有解决问题的思路,而不是有了思路却死活不能实现,这就是平时积累的基础知识不够。今年World Final的总冠军是波兰华沙大学,其成员出自于数学系而非计算机系,这就是一个鲜活的例子。竞赛中对于基础学科的涉及主要集中于数学,此外对于物理、电路等等也可能有一定应用,但是不多。因此,大一的同学也不必为自己还没学数据结构而感到不知从何入手提高,把数学捡起来吧!下面我来谈谈在竞赛中应用的数学的主要分支。 1、离散数学——作为计算机学科的基础,离散数学是竞赛中涉及最多的数学分支,其重中之重又在于图论和组合数学,尤其是图论。 图论之所以运用最多是因为它的变化最多,而且可以轻易地结合基本数据结构和许多算法的基本思想,较多用到的知识包括连通性判断、DFS和BFS,关节点和关键路径、欧拉回路、最小生成树、最短路径、二部图匹配和网络流等等。虽然这部分的比重很大,但是往往也是竞赛中的难题所在,如果有初学者对于这部分的某些具体内容暂时感到力不从心,也不必着急,可以慢慢积累。 竞赛中设计的组合计数问题大都需要用组合数学来解决,组合数学中的知识相比于图论要简单一些,很多知识对于小学上过奥校的同学来说已经十分熟悉,但是也有一些部分需要先对代数结构中的群论有初步了解才能进行学习。组合数学在竞赛中很少以难题的形式出现,但是如果积累不够,任何一道这方面的题目却都有可能成为难题。 2、数论——以素数判断和同余为模型构造出来的题目往往需要较多的数论知识来解决,这部分在竞赛中的比重并不大,但只要来上一道,也足以使知识不足的人冥思苦想上一阵时间。素数判断和同余最常见的是在以密码学为背景的题目中出现,在运用密码学常识确定大概的过程之后,核心算法往往要涉及数论的内容。 3、计算几何——计算几何相比于其它部分来说是比较独立的,就是说它和其它的知识点很少有过多的结合,较常用到的部分包括——线段相交的判断、多边形面积的计算、内点外点的判断、凸包等等。计算几何的题目难度不会很大,但也永远不会成为最弱的题。 4、线性代数——对线性代数的应用都是围绕矩阵展开的,一些表面上是模拟的题目往往可以借助于矩阵来找到更好的算法。 5、概率论——竞赛是以黑箱来判卷的,这就是说你几乎不能动使用概率算法的念头,但这也并不是说概率就没有用。关于这一点,只有通过一定的练习才能体会。 6、初等数学与解析几何——这主要就是中学的知识了,用的不多,但是至少比高等数学多,我觉得熟悉一下数学
上的相关内容,至少要知道在哪儿能查到,还是必要的。 7、高等数学——纯粹运用高等数学来解决的题目我接触的只有一道,但是一些题目的叙述背景往往需要和这部分有一定联系,掌握得牢固一些总归没有坏处。 以上就是竞赛所涉及的数学领域,可以说范围是相当广的。我认识的许多人去搞信息学的竞赛就是为了逼着自己多学一点数学,因为数学是一切一切的基础。 三、数据结构与算法是真正的核心 虽然数学十分十分重要,但是如果让三个只会数学的人参加比赛,我相信多数情况下会比三个只会数据结构与算法的人得到更为悲惨的结局。 先说说数据结构。掌握队列、堆栈和图的基本表达与操作是必需的,至于树,我个人觉得需要建树的问题有但是并不多。(但是树往往是很重要的分析工具)除此之外,排序和查找并不需要对所有方式都能很熟练的掌握,但你必须保证自己对于各种情况都有一个在时间复杂度上满足最低要求的解决
。说到时间复杂度,就又该说说哈希表了,竞赛时对时间的限制远远多于对空间的限制,这要求大家尽快掌握“以空间换时间”的原则策略,能用哈希表来存储的数据一定不要到时候再去查找,如果实在不能建哈希表,再看看能否建二叉查找树等等——这都是争取时间的策略,掌握这些技巧需要大家对数据结构尤其是算法复杂度有比较全面的理性和感性认识。 接着说说算法。算法中最基本和常用的是搜索,主要是回溯和分支限界法的使用。这里要说的是,有些初学者在学习这些搜索基本算法是不太注意剪枝,这是十分不可取的,因为所有搜索的题目给你的测试用例都不会有很大的规模,你往往察觉不出程序运行的时间问题,但是真正的测试数据一定能过滤出那些没有剪枝的算法。实际上参赛选手基本上都会使用常用的搜索算法,题目的区分度往往就是建立在诸如剪枝之类的优化上了。 常用算法中的另一类是以“相似或相同子问题”为核心的,包括递推、递归、贪心法和动态规划。这其中比较难于掌握的就是动态规划,如何抽象出重复的子问题是很多题目的难点所在,笔者建议初学者仔细理解图论中一些以动态规划为基本思想所建立起来的基本算法(比如Floyd-Warshall算法),并且多阅读一些定理的证明,这虽然不能有什么直接的帮助,但是长期坚持就会对思维很有帮助。 四、团队配合 通过以上的介绍大家也可以看出,信息学竞赛对于知识面覆盖的非常广,想凭一己之力全部消化这些东西实在是相当困难的,这就要求我们尽可能地发挥团队协作的精神。同组成员之间的熟练配合和默契的形成需要时间,具体的情况因成员的组成不同而不同,这里我就不再多说了。 五、练习、练习、再练习 知识的积累固然重要,但是信息学终究不是看出来的,而是练出来的,这是多少前人最深的一点体会,只有通过具体题目的分析和实践,才能真正掌握数学的使用和算法的应用,并在不断的练习中增加编程经验和技巧,提高对时间复杂度的感性认识,优化时间的分配,加强团队的配合。总之,在这里光有纸上谈兵是绝对不行的,必须要通过实战来锻炼自己。 大家一定要问,我们去哪里找题做,又如何检验程序是否正确呢?这大可不必担心,现在已经有了很多网上做题的站点,这些站点提供了大量的题库并支持在线判卷,你只需要把程序源码提交上去,马上就可以知道自己的程序是否正确,运行所使用的时间以及消耗的内存等等状况。下面我给大家推荐几个站点,笔者不建议大家在所有这些站点上做题,选择一个就可以了,因为每个站点的题都有一定的难易比例,系统地做一套题库可以使你对各种难度、各种类型的题都有所认识。 1、Ural: Ural是中国学生对俄罗斯的Ural州立大学的简称 ,那里设立了一个Ural Online Problem Set,并且支持Online Judge。Ural的不少题目算法性和趣闻性都很强,得到了国内广大学生的厚爱。根据“信息学初学者之家”网站的统计,Ural的题目类型大概呈如下的分布: 题型 搜索 动态规划 贪心 构造 图论 计算几何 纯数学问题 数据结构 其它 所占比例 约10% 约15% 约5% 约5% 约10% 约5% 约20% 约5% 约25% 这和实际比赛中的题型分布也是大体相当的。有兴趣的朋友可以去看看。 2、UVA: UVA代表西班牙Valladolid大学(University de Valladolid)。该大学有一个那里设立了一个PROBLEM SET ARCHIVE with ONLINE JUDGE ,并且支持ONLINE JUDGE,形式和Ural大学的题库类似。不过和Ural不同的是,UVA题目多的多,而且比较杂,而且有些题目的测试数据比较刁钻。这使得刚到那里做题的朋友往往感觉到无所适从,要么难以找到合适的题目,要么Wrong Answer了很多次以后仍然不知道错在那里。 如果说做Ural题目主要是为了训练算法,那么UVA题目可以训练全方位的基本功和一些必要的编程素质。UVA和许多世界知名大学联合办有同步网上比赛,因此那里强人无数,不过你先要使自己具有听懂他们在说什么的素质:) 3、ZOJ: ZOJ是浙江大学建立的ONLINE JUDGE,是中国大学建立的第一个同类站点,也是最好和人气最高的一个,笔者和许多班里的同学就是在这里练习。ZOJ虽然也定位为一个英文网站,但是这里的中国学生比较多,因此让人觉得很亲切。这里目前有500多道题目,难易分配适中,且涵盖了各大洲的题目类型并配有索引,除此之外,ZOJ的JUDGE系统是几个网站中表现得比较好的一个,很少出现Wrong Answer和Presentation error混淆的情况。这里每月也办有一次网上比赛,只要是注册的用户都可以参加。 说起中国的ONLINE JUDGE,去年才开始参加ACM竞赛的北京大学现在也建立了自己的提交系统;而我们学校也是去年开始参加比赛,现在也有可能推出自己的提交系统,如果能够做成,到时候大家就可以去上面做题了。同类网站的飞速发展标志着有越来越多的同学有兴趣进入信息学的领域探索,这是一件好事,同时也意味着更激烈的竞争,希望大家都能通过竞争锻炼自己、提高自己,并争取成为胜利者。 ACM竞赛介绍与策略 一、ACM竞赛樯芗肮嬖?/p> ACM/ICPC(国际大学生程序设计竞赛)是由ACM(Association for Computing Machinery,美国计算机协会)组织的年度性竞赛,始于1970年,是全球大学生计算机程序能力竞赛活动中最有影响的一项赛事。ACM/ICPC采用赛区选拔的方式产生参加世界决赛学校的资格,2001年,来自全球超过25个地区1141所大学的2362支队伍参加了第26届ACM/ICPC的赛区竞赛。在2002年3月,来自世界各地的约60支队伍,200多名选手参加了夏威夷总决赛的角逐。可以说,ACM国际大学生程序设计竞赛是参赛选手展示计算机才华的广阔舞台,是著名大学计算机教育成果的直接体现,是信息企业与世界顶尖计算机人才对话的最好机会。在过去十几年中,世界著名信息企业APPLE、AT&T、MICROSOFT和IBM分别担任了竞赛的赞助商。中国大陆高校从1996年开始参加ACM/ICPC亚洲预赛,前五届ACM/ICPC亚洲区选拔赛在上海设有赛区,由上海大学主办。2002年,第六届ACM/ICPC亚洲预赛将该在北京设赛区,由清华大学主办。本次竞赛将于2002年10月在清华园拉开帷幕,预计将有超过60所国内外著名大学的上百支队伍参加本次竞赛(这也是北京工业大学首次参加此项赛事)。 ACM竞赛规定,教练是参赛队伍所代表学校的正式教师,每支队伍最多由三名参赛队员组成,每支队伍中至少有两名参赛队员必须是未取得学士学位或同等学历的学生,取得学士学位超过两年,或进行研究生学习超过两年的学生不符合参赛队员的资格,任何参加过两次决赛的学生不得参加地区预赛或者世界决赛。 竞赛中至少命题6题,至多命题10题,比赛时间为5个小时,参赛队员可以携带诸如书、手册、程序清单等参考资料,试题的解答提交裁判称为运行,每一次运行会被判为正确或者错误,判决结果会及时通知参赛队伍,正确解答中等数量及中等数量以上试题的队伍会根据解题数目进行排名,解题数在中等数量以下的队伍会得到确认但不会进行排名,在决定获奖和参加世界决赛的队伍时,如果多支队伍解题数量相同,则根据总用时加上惩罚时间进行排名,总用时和惩罚时间由每道解答正确的试题的用时加上惩罚时间而成。每道试题用时将从竞赛开始到试题解答被判定为正确为止,期间每一次错误的运行将被加罚20分钟时间,未正确解答的试题不记时,地区预赛可以使用的语言包括C/C++和Java,每支队伍使用一台计算机,所有队伍使用计算机的规格配置完全相同。(竞赛具体的软件环境可能根据赞助商的变化而变) 二、关于竞赛的题型分析 Hal Burch通过在1999年春季的分析得出了这样的结论,竞赛的程序设计一般只有16种类型,它们分别是: Dynamic Programming (动态规划) Greedy (贪心算法) Complete Search (穷举搜索) Flood Fill (不知该如何
) Shortest Path (最短路径) Recursive Search Techniques (回溯搜索技术) Minimum Spanning Tree (最小生成树) Knapsack (背包问题) Computational Geometry (计算几何学) Network Flow (网络流) Eulerian Path (欧拉回路) Two-Dimensional Convex Hull (不知如何翻译) BigNums (大数问题) Heuristic Search (启发式搜索) Approximate Search (近似搜索) Ad Hoc Problems (杂题) 很少有人能真正掌握这其中绝大部分的方法,而对于一些包含了这些方法组合与循环的具有挑战性的综合问题,多数选手都无能为力,因为竞赛中的很多试题都需要选手当场作出分析,而不是套用固定的解题格式,这是竞赛的困难所在,也是它的魅力所在。 三、竞赛准备 ACM竞赛不要求使用某一种特定的语言,所以各个队伍可以根据语言的特点和自己的特长选择,如果对语言的原理语法和特点均能做到成竹于胸、滥熟于心,在比赛的过程中就可以大大缩短调试的时间,从而获得优势。 然而编程之道就如武学之道,语言只是各门各派的武功招式,算法和数据结构则好比内功心法和武学原理。内力深厚,任何招式到了手上都能够化腐朽为神奇;掌握了武学原理,更能做到无招胜有招。选手在竞赛中最重要的素质,正体现于对算法和数据结构的掌握和理解上,通过对经典问题的分析,掌握各种算法的应用范围和数据结构的作用与具体实现,是每个选手在平时学习中的重点所在。 四、竞赛策略 临近比赛,在实力上已经难有质的提高,这时我们不妨将注意力转移到竞赛技巧方面,做不成武学道师也学个韦小宝。在ACM竞赛中,一般来说能成功解决半数或以上题目的队伍已经是相当优秀的,解决所有问题近乎天方夜潭,也就是说无论你的实力如何,都还有很大的改进余地,这其中比较重要的就是竞赛的策略。 (1)分工的问题: 团队的配合十分重要,三个队员之间的合理分工可以大大改进解题的效率,根据队员的不同特点,不同的队伍可以采用不同的分配方式,其间一些细节的处理需要三个人有很好的默契。 (2)算法的选择: 在所有可行的算法当中,我们选择的应该是最可行的方法,而不是最高明的方法,这是竞赛与解决问题的一个重要区别,按照熟悉的程度由高到低选择一个算法,通过计算算法的时间和空间复杂度(在必要的情况下)和特殊的测试数据找出一切使该算法不成立的理由,如果找不到就确定该算法并选用相应的数据结构。在确定思路的时候注意比较常见的思维方式分析,比如逆向的分析,对称的分析等等。 (3)程序的编写: 最好首先编写输入和输出的部分,然后逐步细化,一个部分一个部分地填充调试,其间通过适量的注释来刻画程序的逻辑结构和特殊的技巧。在完成全部代码后用一般的测试数据验证代码的正确性,然后处理特殊的情况和边界问题,试图尽可能地找出错误的情况并加以改正。关于程序的优化主要考虑的是最坏情况下所用的时间是否满足要求,优化的程度以题目要求为准,足够即可,尽量避免使用指针和动态分配,在空间允许的情况下一律采用静态分配。 (4)调试中的问题: 调试中会遇到的许多问题需要在事前有所准备并定出总体设计,当然具体的情况还要临场分析,考虑的方面包括程序中的BUG,算法的正确性和数据结构的合理性,什么时候该放弃这个问题,什么时候该返回到先前放弃的问题,是否需要做到或已经做到足够的优化等等。所有关于调试的输入输出都不要删除,将它们注释起来即可。 (5)竞赛中的杂题处理 在竞赛中有时会出现一些新颖的题型,解决它们的算法很难归到经典的算法中去,每个这类的题都有自己鲜明的特点,对于它们根本没有一般的解法。对于这样的挑战,一个新颖的数据结构或一套特殊的循环或判断常常是必须的。解决这种问题的关键在于仔细地阅读题目的叙述,灵感经常来自于将叙述的逻辑条理整理得十分清楚之后,同样,对这类题的优化也是需要的,至少需要避免过多的循环嵌套。 五、编程与竞赛 学习编程并不是为了参加竞赛,竞赛对于多数选手的意义还是在于参与,以及在备战过程中对自己的锻炼和提高。在这一点上,ACM竞赛和其它一系列竞赛是一样的,只是它的影响力和规模大些罢了,所以笔者希望对编程有兴趣的同学都能够关注竞赛,即使不参加,通过了解竞赛中涉及的编程知识达到课内很难达到的高度,这对每个人都是有益无害的。 ACM竞赛试题分析 2002年11月2日 阿拉伯和北非地区第5届地区赛 题目G 蛇和梯子 上一次笔者简单地介绍了ACM/ICPC程序设计竞赛的基本信息和发展状况,这次则试着向大家展示一下其中一个比较简单的题目,并作出一些粗浅的分析,希望能以此让大家有个更感性的认识。 从“蛇和梯子”的问题谈对信息的过滤处理 2002年11月2日 阿拉伯和北非地区第5届地区赛 题目G 蛇和梯子 问题简述:“蛇和梯子”是一个在N*N(0
size*size-1) break; for (l=0;l