ACM竞赛简介
ACM国际大学生程序设计竞赛(ACM/ICPC:ACM International Collegiate Programming Contest)是由国际计算机界历史悠久、颇具权威性的组织ACM学会(Association for Computing Machinery,美国计算机协会)主办,是世界上公认的规模最大、水平最高的国际大学生程序设计竞赛,其目的旨在使大学生运用计算机来充分展示自已分析问题和解决问题的能力。
竞赛的历史可以上溯到1970年,当时在美国德克萨斯A&M大学举办了首届比赛。作为一种全新的发现和培养计算机科学顶尖学生的方式,竞赛很快得到美国和加拿大各大学的积极响应。1977年,在ACM计算机科学会议期间举办了首次总决赛,并演变成为目前的一年一届的多国参与的国际性比赛。迄今已经举办了三十多届。因历届竞赛都荟萃了世界各大洲的精英,云集了计算机界的希望之星,而受到国际各知名大学的重视,并受到全世界各著名计算机公司的高度关注,成为世界各国大学生最具影响力的国际级计算机类的赛事。
最初几届比赛的参赛队伍主要来自美国和加拿大,后来逐渐发展成为一项世界范围内的竞赛。特别是自1997年IBM开始赞助赛事之后,赛事规模增长迅速。 1997年,总共有来自560所大学的840支队伍参加比赛。而到了2004年,这一数字迅速增加到840所大学的4109支队伍并以每年10~20%的速度在增长。
在赛事的早期,冠军多为美国和加拿大的大学获得。而进入上世纪九十年代后期,俄罗斯和其它一些东欧国家的大学连夺数次冠军。来自中国大陆的上海交通大学代表队则在2002年美国夏威夷第26届和2005年上海举行的第29届全球总决赛上两夺冠军。这也是目前为止亚洲大学在该竞赛上取得的最好成绩。赛事的竞争格局已经由最初的北美大学一枝独秀演变成目前的亚欧对抗的局面。
此项赛事的主办目的不仅是培养参赛选手的创造力,团队合作精神以及他们在软件程序开发过程中的创新意识,同时也是检测选手们在压力下进行开发活动的能力。可以说,ACM国际大学生程序设计竞赛是参赛选手展示计算机才华的广阔舞台,是著名大学计算机教育成果的直接体现,是信息企业与世界顶尖计算机人才对话的最好机会。该项竞赛分区域预赛和国际决赛两个阶段进行,各预赛区第一名自动获得参加世界决赛的资格,世界决赛安排在每年的3~4月举行,而区域预赛安排在上一年的9~12月在各大洲举行。
中国内地从1996年开始举办亚洲赛区预赛,前六届赛区设在上海,由上海大学主办。2002年设立了北京和西安赛区,分别由北京清华大学和西安交通大学主办。2003年,第28届ACM/ICPC亚洲赛区预赛在中国有2个赛站:北京和广州。目前,ACM/ICPC亚洲赛区预赛在中国有4个赛站,在各地轮换。
ACM竞赛规则
ACM/ICPC以团队的形式代表各学校参赛,每队由3名队员组成。每位队员必须是入校5年内的在校学生,最多可以参加2次全球总决赛和4次区域选拔赛。
竞赛中至少命题6题,至多命题10题,比赛时间为5个小时,参赛队员可以携带诸如书、手册、程序清单等参考资料,试题的解答提交裁判称为运行,每一次运行会被判为正确或者错误,判决结果会及时通知参赛队伍,根据解题数目进行排名,如果多支队伍解题数量相同,则根据总用时加上惩罚时间进行排名。每道试题用时将从竞赛开始到试题解答被判定为正确为止,期间每一次错误的运行将被加罚20分钟时间,未正确解答的试题不记时。每队在正确完成一题后,组织者将在其位置上升起一只代表该题颜色的气球。
最后的获胜者为正确解答题目最多且总用时最少的队伍。每道试题用时将从竞赛开始到试题解答被判定为正确为止,其间每一次提交运行结果被判错误的话将被加罚 20分钟时间,未正确解答的试题不记时。例如:A、B两队都正确完成两道题目,其中A队提交这两题的时间分别是比赛开始后1:00和2:45,B队为1: 20和2:00,但B队有一题提交了3次。这样A队的总用时为1:00+2:45=3:45而B队为1:20+2:00+0:40=4:00,所以A队以总用时少而获胜。
与其它计算机程序竞赛(例如国际信息学奥林匹克,IOI)相比,ACM/ICPC的特点在于其题量大,每队需要5小时内完成6~10道题目。此外,一支队伍的3名队员只有1台电脑,使得时间显得较为紧张。因此除了扎实的专业水平,良好的团队协作和心理素质同样是获胜的关键。
ACM竞赛级别
ACM程序设计竞赛可以分为4个级别:本地比赛(Local Contest)、区域赛(Area Contest)、分区赛(Regional Contest)和总决赛(Final Contest)。
ACM/ICPC竞赛考核要求
程序设计竞赛与软件工具的使用不同,它要求编程者以某种高级语言为媒介,通过构造算法去解决由现实生活中抽象出来的问题,这些问题非一般工具软件能解决。程序设计对人的能力要求是多方面的。编程者不仅要熟悉计算机语言的语法,而且还要具备:
1、扎实的数学基础和算法知识,能够对问题或者客观存在的事务及其所要解决的问题产生正确认识和理解,包括弄清楚事物属性、行为及其彼此之间的关系。
2 、娴熟的编程技术,能够把对问题及其方法的认识描述出来,最终产生一个计算机能够理解和执行的系统实现。
3 、相应的实践能力和创造能力,能够独立思考、提出质疑,拓延思路、洞悉规律,创造性地运用知识于不同的问题情景。
4 、如果真正参加竞赛,那么对心理素质的要求非常高。落后时不急不躁,领先时不盲目乐观,方能立于不败之地。同时,大学生的ACM 竞赛是三人团队共用一台机器,这对培养集体合作精神很有好处。
程序设计竞赛主要考的是数据结构、算法和数学模型,这些知识是本科阶段主要的专业基础课程,所以程序设计竞赛一定程度上可以反映出一个学校的教学水平,这 也是为什么程序设计竞赛为什么规模越来越大的一个原因。正因为程序设计能比较客观地反映人的综合素质,因此,国际、国内的各种大学生和中学生信息学方面的 竞赛都把程序设计作为考核内容。
在线评测系统(Online Judge)
国内:
浙江大学ACM网址:http://acm.zju.edu.cn/
北京大学ACM网址:http://acm.pku.edu.cn
哈尔宾工业大学ACM网址:http://acm.hit.edu.cn
国外:
USACO:http://ace.delos.com/usacogate/
西班牙网站http://acm.uva.es
俄罗斯站点http://acm.timus.ru
讨论区:
武汉大学、北京大学、南京大学、上海交大、中山大学等大学BBS上的ACM/ICPC讨论区
ICPC官方网站:http://icpc.baylor.edu/icpc/
ACM基本算法分类
一、动态规划
参考资料:
刘汝佳《算法艺术与信息学竞赛》《算法导论》
推荐题目:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1141
简单
http://acm.pku.edu.cn/JudgeOnline/problem?id=2288
中等,经典TSP问题
http://acm.pku.edu.cn/JudgeOnline/problem?id=2411
中等,状态压缩DP
http://acm.pku.edu.cn/JudgeOnline/problem?id=1112
中等
http://acm.pku.edu.cn/JudgeOnline/problem?id=1848
中等,树形DP。可参考《算法艺术与信息学竞赛》动态规划一节的树状模型
http://acm.zju.edu.cn/show_problem.php?pid=1234
中等,《算法艺术与信息学竞赛》中的习题
http://acm.pku.edu.cn/JudgeOnline/problem?id=1947
中等,《算法艺术与信息学竞赛》中的习题
http://acm.pku.edu.cn/JudgeOnline/problem?id=1946
中等,《算法艺术与信息学竞赛》中的习题
http://acm.pku.edu.cn/JudgeOnline/problem?id=1737
中等,递推
http://acm.pku.edu.cn/JudgeOnline/problem?id=1821
中等,需要减少冗余计算
http://acm.zju.edu.cn/show_problem.php?pid=2561
中等,四边形不等式的简单应用
http://acm.pku.edu.cn/JudgeOnline/problem?id=1038
较难,状态压缩DP,《算法艺术与信息学竞赛》中有解答
http://acm.pku.edu.cn/JudgeOnline/problem?id=1390
较难,《算法艺术与信息学竞赛》中有解答
http://acm.pku.edu.cn/JudgeOnline/problem?id=3017
较难,需要配合数据结构优化(我的题目^_^)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1682
较难,写起来比较麻烦
http://acm.pku.edu.cn/JudgeOnline/problem?id=2047
较难
http://acm.pku.edu.cn/JudgeOnline/problem?id=2152
难,树形DP
http://acm.pku.edu.cn/JudgeOnline/problem?id=3028
难,状态压缩DP,题目很有意思
http://acm.pku.edu.cn/JudgeOnline/problem?id=3124
难
http://acm.pku.edu.cn/JudgeOnline/problem?id=2915
非常难
二、搜索
参考资料:
刘汝佳《算法艺术与信息学竞赛》
推荐题目: