专栏首页ACM算法日常Re: 从零开始的程序设计竞赛(零)

Re: 从零开始的程序设计竞赛(零)

转载声明:本文来源于知乎专栏《Dai 的程序设计竞赛瞎扯自动机 》,已获得原作者Dai@NeverLand的允许,禁止二次转载。

前言

跟之前提起过的一样,我准备挖个新坑,写写怎么从零开始参加程序设计竞赛。

对于大部分同学来说,如果期望能看到什么刷题秘籍,那可能是没有的,毕竟我刷题实力不足,比参加过 Final 的@ftiasch之流的竞赛偶像差太多了……不过在圈子里摸爬滚打了这么多年,当个嘴巴玩家总还是可以的,所以这系列文章主要应该会分成三个部分:

一、如何参加比赛?

二、个人应该从哪些方面下手训练?

三、组队应该从哪些方面下手训练?

其中如何参加比赛的部分,可能会把初级内容和高级内容分拆出来,也可能不会,看我心情。

尴尬的是,我默认看我专栏的一般是学生,很少有老师,但很多内容其实是写给老师的,毕竟训练这东西靠自己能成的人总是少数,这很多时候也是所谓“弱校”难出成绩的重要原因,因为方法不得当,学生更多只能依靠自己求学,这个摸索成本就要大得多。

全系列估计会有比较长时间的连载,每一篇篇幅不长,主要是我写作时间和能力所限,不可能能随随便便就编出几万字的东西。与此相关的是,我应该(?)开通了赞赏功能,在此说明:我不怎么缺钱(当然也不是不缺,谁会嫌钱多呢?),这个功能纯粹是想看看有没有人对挖坑不填很愤怒,如果你表达了愤怒,我会比较羞愧地稍微……写快一点,但不保证(噗嗤)。如果真的有人赞赏的话(目前看来可能不咋可能),在系列文章结束时我会把所得全部捐给「百万森林」计划,大家多呼吸一点新鲜氧气吧(……),也欢迎反馈这个功能好用不好用(我自己是看不到有没有按钮的……)

关于转载,请参考CC BY-NC-ND 4.0。商业使用的请提前联系我获得许可(不联系使用的,律师含警告(?)。

是什么?

既然是「从零开始」,那当然就是从介绍比赛开始讲起——说到这里,我知道很多人会开始浮现起一段话,那个被印在几乎所有赛区的竞赛手册、新闻稿、领导讲话之类地方的,什么什么历史什么什么最具影响力的大学生程序设计竞赛之类的一段话,但我想讲的不是这个。

毕竟,现在有了 CCPC 了嘛(滑稽)。

而且还有天梯赛是吧(再次滑稽)。

我认为,目前意义上的,「程序设计竞赛」是:

在较短的限定时间内,用计算机实际编程在严格的限制下解决一个或多个高度抽象的精心设计过的问题的竞赛。

从这点上来看,程序设计竞赛跟你的 C 语言课程期末考试可能没有本质上的区别,如果你的 C 语言课已经是上机考的话。当然如果贵校还是纸质考试的话,欢迎了解一下我们的产品 (被打死

PTA | 程序设计类实验辅助教学平台pintia.cn

就我了解的情况来看,在这类竞赛中有一些地方可能与你平时的编程练习题有一些差别:

(1)一般不用输入所谓的「输入提示语句」

这个陋习来自于很多 C 语言入门书都喜欢添加一些提示信息,比如 「Please input a number」之类的,学生学的时候也不太懂是个什么玩意儿,抄上去感觉还蛮好玩,于是就动不动就 input a number 了……

然而这个东西实际上并没有什么卵用,尤其在电脑判卷的过程中只会浪费系统资源(参考下文),所以在一个水平比较过关的程序设计竞赛中,一般不会要求输出这类字符串。

(2)对程序的运行时间、空间有所要求

不要说学生了,很多老师一开始做题,也在问一个问题:为什么我的程序运行超时啦?明明我样例跑的很快,甚至是一闪而过的?

这里就要说到软件测试了,但是说起来好麻烦啊(我也不会)。所以我简单的说一下,一般程序设计竞赛中,要测试你程序是否正确,一般都符合以下两个原则:

  1. 黑箱测试:不看你代码如何编写,只看程序对于输入结果能否输出正确的结果。
  2. 隐藏数据:系统用于测试你程序的数据与你能看到的数据不一致。

虽然特殊情况下这两个规则都有可能不符合(例如第一点,我就遇到过裁判看我程序给我返回运行时错误,但实际上是错误答案的事;第二点,以前的 Google Code jam 以及提交答案类的题目都是明显的反例),但大部分情况仍然是正确的。

在这个大前提下,出于系统资源以及考察的因素,给程序的运行设下限制是最现实也最合理的方式。举个栗子,大家都喜欢的输出素数,如果不设置限制,那你写了个枚举每个数试除的程序,范围大点,估计到比赛完了程序还没运行结束……

(3)对输出有严格的规定和要求

前面也说到了,因为是黑箱测试(很多甚至是自动测试),因此要判断一个程序是否正确,人或程序所要做的,就是把准备好的输入数据喂给你的程序,然后看看你程序输出是否正确。判定正确显然只能与现有的“标准答案”做对比,毕竟现在人工智能可能还没有牛逼到可以直接忽略你输出的「The answer is」之类的提示语句。也是因为如此,所以多个空格少个空格,或是打错单词有时也会躺枪,但这没啥办法……

为什么?

为什么要打这个比赛呢?我就不说那些「我感觉比赛很好玩」之类的废话了,大家都关心实际的东西,那么实际的东西是:

  1. 至少在现在,参加比赛的学生能够进入好企业的概率仍然比没参加比赛的学生大一些。

要注意的是,很多人会将上面的话理解为「程序设计竞赛能够培养选手综合能力」之类的方面,但我必须指出这其实是不正确的——真正的事实是,现在中国计算机教育的水平之低下到了一定程度,以致于学了四年计算机(无论是计算机科学还是软件工程吧)还无法独立编程的学生大有人在,而企业肯定不希望花费精力去面试这样的学生,毕竟面试的成本其实是很大的。

程序设计竞赛,尤其是比较高水平的 ICPC/CCPC 竞赛,是一个「筛选器」:你在这个比赛拿到了奖项,起码你会写程序的概率比别人要大得多,企业的招聘成本降低了。

仅此而已。

因此知乎上有很多诸如「不打比赛是不是就找不到好工作」之类的问题,我觉得显然不是的。不过话又说回来了,你要硬邦邦写点牛逼项目还是很有用的,但如果只是划划水的话可能还不如打比赛呢。

2. 能够认识很多人。

从事实上而言,目前竞赛选手已经成为了很多高新创业企业的技术核心,比如图森(TuSimple),脸艹,啊不是,Face++,依图,当然还有大家熟知的 Pony.ai 等等公司。因此无论是在现在,亦或是将来,在圈子里认识更多的人总是有好处的;毕竟以后工作了,你很可能来来回回都会碰到这群人……而以我的了解来看,对于国内大部分的计算机学生来说,稀烂的英语水平可能也不足以支撑利用 Github 等方式进行社交的路子,因此这可能是唯一的途径了。

3. 对老师而言……

有些学校可能承认这些奖项,有些学校则可能不承认,但无论如何,这至少是一个批量生产出路光明学生的一个路子,当学生都去了 BAT 等大公司的情况下,对老师应该是有名声上的进展的,也可以因此建立一个良好的关系网……其他的我就不展开说了,毕竟我觉得这方面来说参与的老师肯定比我想的要清楚。我会把这部分更细的内容放到下一节里讲,尽量提供一些参考资料供老师们参考。

怎么办?

这就涉及到本系列文章最核心的部分了。下次再讲:)

本文分享自微信公众号 - ACM算法日常(acm-clan)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-11-19

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 多线程:为什么在while循环中加入System.out.println,线程可以停止

    这个我们都知道,由于 stopReqested 的更新值在主内存中,而线程栈中的值不是最新的,所以会一直循环,线程并不能停止。加上 Volatile 关键字后,...

    用户1655470
  • python基础类型(一):字符串和列表

    注意到最后三个的单双引号是嵌套使用的,但是最后一个的使用方法是错误的,因为当我们混合使用两种引号时必须有一种用来划分字符串的边界,即在两边的引号不能出现在字符串...

    渔父歌
  • 理解BitMap算法的原理

    位图:一种常用的数据结构,代表了有限域中的稠集(dense set),每一个元素至少出现一次,没有其他的数据和元素相关联。在索引,数据压缩,海量数据处理等方面有...

    我是攻城师
  • Diss所有深度生成模型,DeepMind说它们真的不知道到底不知道什么

    深度学习在应用层面获得了巨大成功,这些实际应用一般都希望利用判别模型构建条件分布 p(y|x),其中 y 是标签、x 是特征。但这些判别模型无法处理从其他分布中...

    机器之心
  • 一些常用的算法技巧总结

    数组的下标是一个隐含的很有用的数组,特别是在统计一些数字,或者判断一些整型数是否出现过的时候。例如,给你一串字母,让你判断这些字母出现的次数时,我们就可以把这些...

    帅地
  • 200行代码,一行行教你自制微信机器人

    1) 用一个windows客户端工具运营公众号,真的很局限。虽然工具的功能很强大,能自动添加好友,自动拉好友入群,关键字回复等等,但是有一个绕不开的点,它是一款...

    用户1634449
  • 『高级篇』docker之Mesos集群架构图(23)

    IT故事会
  • 一张图解释负载均衡

    首先当大量用户访问时候,先请求到nignx服务器,因为nignx对于高并发支持较好,所以由nignx服务器将访问需求分配给不同的apache服务器,apache...

    smy
  • 迷人又诡异的辛普森悖论:同一个数据集是如何证明两个完全相反的观点的?

    在辛普森悖论中,餐馆可以同时比竞争对手更好或更差,锻炼可以降低和增加疾病的风险,同样的数据集能够用于证明两个完全相反的论点。

    大数据文摘
  • TFS2018环境搭建一硬件要求

    TFS可以安装在Windows Server和Windows PC操作系统中,但是TFS2018和2018只支持64位操作系统中,早期的版本没有操作系统的位数限...

    郑小超.

扫码关注云+社区

领取腾讯云代金券