ACM/ICPC

Report
2012年ACM/ICPC
校集训队招新讲
6-1 万山川
ACM/ICPC
 为什么学?
 学什么?
 怎么学?
程序设计竞赛的意义
 Go to fly?
 逃体能、公差?
 保研加分?
 ……
程序设计竞赛的意义

•
•
•
•
•
习惯、态度、方法、能力:
自主学习的能力
分析判断的能力
团队协作的能力
解决问题的能力
安身立命的能力
“深入开展信息化条件下的军事训
练,增强基于信息系统的作战能
力。”
——十八大报告
“全军要深刻认识军队在国家安全
和发展战略全局中的重要地位和
作用,全面提高信息化条件下威
慑和实战能力,坚决维护国家主
权、安全、发展利益。”
——中央军委扩大会议
 计算机软件技术——
•
信息化战争的智慧之神
 计算机技术——
•
信息化战争的操控中枢
应用广泛
 专业领域:人工智能、计算机系统、数字系统
设计、电子系统设计、信息技术与系统、软件
工程、人机互动、多媒体技术、电脑游戏开发、
网络信息安全
 交叉学科:计算机辅助、计算机仿真、金融计
算机学、信息系统管理、生物信息学、分子计
算学、认知科学
相关赛事
 Google Code Jam
 百度之星
 Facebook骇客杯
 VK Cup
 Topcoder Open
 网易有道难题
 腾讯编程马拉松
 搜狐杯智能体大赛
 ……
百度之星
 全国总决赛
 T恤、奖杯、度度熊
 参观百度大厦
 内部技术讲座
 万国击剑
 德云社相声
 结识牛人
 开拓视野
 ……
传奇人物
 Petr Mitrichev
 楼天城
 戴文渊
Petr Mitrichev



假如普京在一个对的时间从克林姆林宫的窗户往外
看,他有可能看到河对岸Google莫斯科办公室里那
个世界上最牛的程序员。
Petr Mitrichev,现年27岁。他现在在Google俄罗斯
分公司的搜索引擎部门工作,只在休闲时去参加编
程比赛,但仍然排名第一。
他的冠军头衔则来自各项编程大赛。在这些比赛中,
程序员会为了现金奖励、旅游机会、以及在世界上
任何其他地方都无法获得的荣誉,编写代码。
 “当你在一个竞赛中解决一个难题时,你就会有
一种成就感。”
 “这类比赛的美在于,
它是完全自动的,不会
牵涉任何的人为评判。”
 “我之所以会坚持参加
各类比赛,是因为编程
在我看来就是一种休闲。
你可以选择看电视节目,
但你也可以选择参加Top
Coder每周的比赛。”
楼天城
•
•
•
•
•
•
•
ACRush
中国大学生编程竞赛第一人
常以一人单挑一个团队,人称“楼教主”
2004年国际信息学奥林匹克竞赛金牌
2007、2009年ACM/ICPC全球总决赛亚军
2008年谷歌编程挑战赛冠军
2012年9月入职美国谷歌公司,负责社交网络
 “有谣言说三国杀游戏是你发明的,是真的吗?”
•
“这个不是谣言,是真的。”
 “在IT届有两类公司,一类以谷歌为代表,一直做
别人做不到的事,向世人证明再难的事也可以做
出来;一类以苹果为代表,做别人都在做的事,
却也证明一件事能做到多好。”——楼天城
戴文渊
•
•
•
•
•
•
2005年ACM/ICPC全球总冠军
先后3次获得亚洲区域赛冠军
学术论文多次被SCI及国际顶级学术会议AAAI和
ICML收录
上海交大十大新闻人物之年度神话人物
2009年放弃继续攻读博士学位入职百度
现任百度商务搜索部主任架构师、资深专家、
首席科学家,百度凤巢策略团队模型组技术负
责人
 出生于1983年的戴文渊今年虚岁30岁,上个月,
他率领“凤巢个性化投放策略”团队获得百度公司
设立的 “最高奖”。他
的团队成员更加年轻,绝
大部分毕业不过两、三年,
7名年轻人高高兴兴地分享
了百万美元奖金。
 当一些同龄人还处于事业的
摸索期,戴文渊和他的伙伴
们已翻越了职业生涯的一座
高峰,并向新的方向前行。
 曾有一位计算机非常厉害的前辈去了美国的伊
利诺斯大学,但很快被世界著名的网络公司挖
走。戴文渊知道后感到非常惋惜。他为了不被
美国的商业诱惑,潜心研究学问,放弃了出国
的机会,留在了上海交大读研。
 “学校的资源有限,经过一段时间之后我发现也
许读下去做不出自己想要的。你自己想做什么
自己可以控制,但是外部环境也很重要,没有
资源的话也做不出想要的效果。我的个人兴趣
在于数据驱动,百度最大的优势就是数据,所
以在公司的环境下才能做出来。实验室平台还
是比较局限的。”
讲这些的目的?
“计算机信息是一种日新月异的科技,昨天的
技术,打不赢明天的战争,在信息领域,闭门造车
的防护是被动挨打,我们应该走出去,向世界学习,
只有这样,我们的信息安全才能得到有效保证。”
——李聪娜 第12届全军学习成才标兵
Introduction to Competitive
Programming Contests









Mathematics
Data Structures
Dynamic Programming (DP)
Combinatorial Games
Basic Graph Algorithms
Shortest Path Algorithms
Network Flow Problems
Computational Geometry
String Algorithms
考察内容
 程序设计技巧
 算法知识
 数据结构
 数学功底
 团队协作能力
 “算法是计算机科学领域最重要的基石之一,但
却受到了国内一些程序员的冷落。”
 “学习计算机算法和理论更重要,因为计算机
语言和开发平台日新月异,但万变不离其宗的
是那些算法和理论,例如数据结构、算法、编
译原理、计算机体系结构、关系型数据库原理
等等。”
 “真正学懂计算机的人(不只是‘编程匠’)都对
数学有相当的造诣,既能用科学家的严谨思维
来求证,也能用工程师的务实手段来解决问
题——而这种思维和手段的最佳演绎就是“算
法”。”
“在高能物理研究方面,很多实验每秒钟都产生几个
TB的数据量。但因为处理能力和存储能力的不足,
科学家不得不把绝大部分未经处理的数据丢弃掉。
可新元素的信息很有可能就藏在我们来不及处理的
数据里面。”
 “同样的,在其他任何领域里,算法都可以改变人类
的生活。例如人类基因的研究,就可能因为算法而
发明新的医疗方式。在国家安全领域,有效的算法
可能避免下一个911的发生。在气象方面,算法可以
更好地预测未来天灾的发生,以拯救生命。”
 “所以,如果你把计算机的发展放到应用和数据飞速
增长的大环境下,你一定会发现,算法的重要性不
是在日益减小,而是在日益加强。”

比赛规则







独特的赛制(黑箱测试,类Moodle)
以队为单位, 每队不超过三人
高中毕业不超过五年(Collegiate)
合作—每队仅一台计算机
可携带一切纸制资料
5小时 8~12道题
排名: 完成的题目数量 使用的时间。
ACM适合于任何人,无论你有怎样的基础,成绩只取决于你后天的努力
比赛形式
读题
比较标准输出
写代码
思考
输出
测试
数据
提交
错误 – 修改源代码
正确 – 得到一个气球
训练方法
 Online Judge
 Compile Error
 POJ
 Runtime Error
ZOJ HDOJ
 Topcoder
 CodeForces
 Time Limit Error
 Wrong Answer
 Accepted
推荐书籍
 刘汝佳
•
•
•
清华大学出版社
《算法竞赛入门经典》
《算法竞赛入门经典:训练指南》
《算法艺术与信息学竞赛》
 《算法导论》(Introduction to Algorithms)
 《计算机程序设计艺术》(TAOCP)
“你还有什
么借口不好
好编程,饭
碗都要被大
妈抢了!”

similar documents