0%

最后的算法竞赛经历

本文转载自我的知乎回答如何评价北京理工大学第十五届“连山科技”程序设计大赛?

最近时间开始多了起来,我准备多写点东西。

如何评价北京理工大学第十五届“连山科技”程序设计大赛?

光阴似箭,从大一我第一次参加新生赛,到昨天最后一次参加校赛,已经过了三年了。最开始的时候,还能见到14级的强神、庆神,现在20级的新生都已经在比赛中大放光彩了,真是让人感觉时光荏苒;不过,年年比赛都能看到易大师、龙神、牟神、沈帝等人的身影,又仿佛一切都没变过,我的时间永远定格在大一的暑假集训。做为一个退役选手,本次比赛的意义对我的意义已经不在于过了多少题,更多的是一些比赛之外的东西。

按照老规矩,我还是会完全站在个人视角,先对比赛的出题质量、服务质量进行评论,再以时间顺序从网络赛到正赛谈个人经历和感想。个人感想可能有点多,可以直接跳到最后面看总结。

评价

由于这次命题组人数较多,且有龙神等出题经验丰富的前辈,整体试题质量极高。从题型覆盖看,模拟、签到(排序)、dp、博弈、字符串、图论、计算几何、构造……应有尽有;从难度分布来看,正赛6题快银,8题快金,冠军队更是以唯一10题队的身份稳稳占据榜首,题目区分度十分明显。具体到每道题上,不少题目出得十分精彩,其中最令人印象深刻的是网络赛G题构造,讨论完普遍情况,特判完所有特殊情况后,一发畅快淋漓的AC令人意犹未尽。

但是,题目的质量仍有提升空间。从题面上看,亮皇出的热身赛J题中文语法混乱、逻辑不清,参赛者不得不凭借自己的脑补能力把题意理解清楚。正赛最后一题M题对于d的解释不够清楚。正赛又是网络流,又是高斯消元,又是后缀自动机,需要使用模板的地方略多。

服务质量仅讨论中关村正赛。打印服务一开始不能正常工作,且奇慢无比,严重阻塞了三线程的运行。编译环境恶劣,只有不带c++11的devc稍微好用,codeblocks一开始没编译器,后来编译器不能在32位系统上运行。比赛完回到良乡后,滚榜都快结束了,冷餐就剩了一点“给中关村选手准备的食物”。好的地方不是没有,志愿者和裁判组倒是十分积极努力地在提升选手的参赛体验。虽然很多问题是客观问题,再怎么样也不能改变,但该喷还是得喷。

网络选拔赛

我一直很想再参加一次团队算法竞赛,但比赛报名前夕才发现没队友。幸好喵神把我拉进了她们队里,三个退役选手组了个队。现在的我,回想起那个因找到队伍而欣喜的下午,绝对想不到之后我竟然会成为一个工具人。报名开始后,喵神不肯做队长,要我去报名时,我就感到不对劲。之后,各种繁琐的流程接踵而至。又是填报名信息,又是接邮件记密码,之后还要领衣服,比赛完了还要填获奖信息。热身赛我一个人去检查环境,比赛完我一个人回去领奖。虽然如此,比赛的时候大家还是在愉快地讨论,参赛体验还是不错的。

网络赛的时候,为了创造更好的参赛体验,不让学弟们感到太多的压力,我们选择不发挥全力,在实力上有所保留(实际上是,队友不在校内,编程环境不太好,代码只能让我提交)。最终我们过了9题,既向大家展现了实力,又把宝贵的前几名让给了学弟们,可谓是用心良苦。

比赛开始前一小时,我去cf随便写了几题。当我熟练地在5秒内敲完for(int i =0; i < n; i++)时,我感到一切都回来了。手速、算法知识、编程技巧,我完完全全地找回了它们。我自信地迎接着网络赛的到来。

比赛一开始,一股熟悉的想抢一血的冲动涌上心头。我本能地点开I题,浏览题目之后,发现事情不对,立马换题。抱着想抢一血的功利心,我不想花费一分一秒在看榜上。很快,我准备写F题。

F题很明显是个排序签到题,写惯了正经代码的我,从这样一道算法少、流程繁琐的题开写是十分妥当的。可惜意识尚在,熟练度尽失。我仔仔细细地读了遍题,工工整整地定义了类和两个排序函数,main函数里用简短优美的代码完成了整个算法流程。我颤颤巍巍地把代码上传,确认再三后才点击了提交。焦躁地按了几下F5刷新后,屏幕上出现了一行绿色的CORRECT。看到代码通过后,我体会到久违而熟悉的成就感。此时比赛已过去21分钟,不仅F题一血没了,其他水题也被陆陆续续地通过了。但我的斗志丝毫没有衰退,带着首次过题的成就感BUFF,心态良好地开始跟榜做题。

我看L题过题人数最多,就开始写L题。L题是个超级签到题,用第一个月学C语言的知识就能轻松做出。

A题一看就是个“模拟”题。久经战阵的我,发现了题目和数据的不一致性,并且知道样例才是正确的。我用一个比较繁琐的方法才把图片导入进代码:先读入样例文件,把空格和符号转化成01串,再把01串粘贴进代码。我及其稳健地一次通过A题。

B题过的人也不少,但乍看之下不是什么简单的题:和普通背包问题类似,你要保证不超出背包容量的前提下选择物品,获得最大价值。只是每次选择的物品不大于上次物品的重量。但仔细观察数据范围可以发现,物品数、重量全都不超过100。我一边写代码,一边以极强的基本功在心里推出转移函数,顺利过了B题。

J题全是用中文写的,但读起来和天书一样,在跟榜做题的原则下,我不得不开了这题。题目给了一行数,每个数字表示一个物品;又给了一个每种物品的数量要求。你要从这行数中选一个连续区间,使得选的物品满足物品数量要求,求最小区间长。数的规模是1e6。我看答案是单调的,先考虑了二分答案,再想到用尺取判断答案。后来发现不用二分直接尺取就可以过了。不过出题人比较善良,加了二分也没有t。J题也被轻松通过。

这个时候,我的队友加入了战场。湛学姐读完了D题E题,以极强的思考能力迅速理论AC了这两道题。于是,我选择去实现E题。

E题是计算几何题,给出平面上若干点,保证不存在三点共线。要求找到一对点,使得过这两点的直线能恰好平分剩余的点,或者说明这样的点对不存在。由于要求正好平分,奇数个点的情况就之前pass了。对于偶数个点,以某个点为原点进行极角排序,找到排序后最中间的点。原点和中间点就是答案。极角排序的原点可以选择最左下角的点,但比赛的时候我先找了下凸包,再选了凸包上一点。由于我对自己的板子很不熟悉,WA了两发。但是,此刻我知道我不能再浪了。为了契合我们的队名,我发出了“从现在开始,不会再WA”的宣言。

喵神负责写D题,似乎看出了只需计算素因子贡献就行了,一次性顺利过题。

湛学姐又读完了C题,快速给出了做法。我用两分钟时间看完并理解了转述的题意和解法,用二十分钟稳健地AC这题。题目给了一个元素不重复的数组,在保持元素不重复的前提下,可以进行一种操作,操作每次可以把数组里的一个数转换成另一个数。现在给出数组的初始状态和操作若干次之后的状态,问最早需要操作几次及具体方案。一个数在被转换之前,需要保证转换之后的数不在当前的数组中出现。因此,如果数组初始状态和最终状态中不同位置出现相同数字,可以对把这两个位置连一条有向边,表示对两个位置操作的先后性。最终得到的图如果没有环,可以直接按着有向边的顺序进行操作;如果出现环,就把某个位置先修改成一个tmp值,把环拆掉,再进行操作。

剩下的题目中最有希望的是G题。G题过题人数较多,且是构造题,想到就能过。题目要求用两种形状的积木拼出一个给定长宽的矩形,问方案是否存在,若存在要输出具体方案。积木的形状是

1
2
***      **
* *

经讨论,2X3,2X5~2Xn都能构造出来。4X4特判。3X5无法构造。仅需讨论5X5能否构造即可构造出剩余比较大的矩形。湛学姐以极强的洞察力和丰富的想象力,构造出了5X5的方案。我负责把代码写出来。由于这题要求输出方案,代码极其繁琐。我凭借着多年积累的结构化编程经验,把每个操作模块化实现,先后实现了声明新积木、画积木、转积木、反转矩形、画矩形等函数。整个程序变量名、函数名清楚易懂,代码逻辑清晰,堪称代码中的典范,入选世界10大优美ACM代码也不令人奇怪。最终2发AC,第一发WA在了2X2上。

后来学姐们发现I题是个原题,以前打多校赛的时候写过,本来准备粘一份代码。但喵神坚持着网络选拔赛过题影响正赛RP的封建迷信,拒绝了这种做法。我也秉承着给学弟们保留信心的做法,没有过题。网络赛就这样结束了。很久没有这么爽快地过题,我感到神清气爽。

正赛

刚才,有个朋友,和我说:“帆神,写个答案吧。”

我说:“怎么回事?”他给我发了一个知乎链接,我一看,噢,原来是佐天,有一个竞赛,叫“连山科技”,算法竞赛。我和两个学姐,退役选手,一个研一,一个研二,参加了比赛。

比赛前,我说:“加入你们,让你们丢了最佳女队,不好意思。”塔们说:“没事,你可以carry。”我说:“我carry不了,但我们可以抢一血。按传统的比赛情况来看呢,我是抢一血的。去年校赛,前年新生赛,我的队伍都拿到了全场一血,啊。(笑)”

塔们也很服气,说可以试试。比赛一开始,喵神啪地一下就撕开试题册,很快啊。然后就是,一个找题,一个写题,一个交题。代码提交了,手放到提交键上没有点。这时间,按照传统的比赛情况来看,如果这个键点下去,一血就是我们队的了。塔知道这个代码一定能过,但塔又去检查了一遍代码,塔知道这个代码能提交通过的,啊。但提交一看呢,噢,一血没了,额,大概几分钟前没了,老年人,手速慢了。

但没关系啊。我手里还有题的啊。我老规矩,开局看了I题。发现不对,又去看了G题。G题很明显是个签到题,sg函数,搞个二维的,随便写一写就过了啊。我啪、啪,敲了几下键盘,额这个题目就写好了,很快啊。交上去一看,RE!

喵神说,塔有H题可以写,要我去打印代码。我说:“可以。”我大意了啊,不知道,这个打印机呢,坏了。这个三线程工作,给阻塞了。但我也不傻啊,又去看L题,说:”题目简单,我可以写。“

当时急着过题,我又大意了啊。交了L题,WA了。我一改代码,咋样例又不对呢。湛学姐和我讲了遍题意,噢,原来是题读错了。我说:”对不起对不起,我题读错了,我是乱写的。“喵神又把我踢下去了。

湛学姐急了,塔一直在读题,额,大概有4,5道题,都已经理论AC了。塔说:”I题是个签到题。”塔和我讲了讲题意,一个排序,再随便搞一搞,就好了。噢,原来我上当了。我说:“你来写I题。”总算啊,81分钟,过了第二道,签到题。

之后,我又说:“L题我可以改。”写完了,感觉很正确,交上去,又WA了。喵神看了看,发现有一个排序,有一个小问题,写反了。塔指点了一下,就稍微指点了一下啊,我改完,题就过了。两个小时,我才写了一题。为了表示谦让,我是全队最后一个过题的人啊。

这时间,那个打印机啊,搞好了。G题代码,给送了过来。我一看,噢,一个数组下标,本来是a-b,给写成了b-a。数组下标成了负数,这不RE才奇怪呢。一改完,题就过了。本来开场20分钟就过了,现在两小时20分钟才过,整整120分钟,啊。我们呢,刻意的呢,想多让学弟们,让塔们一些罚时。

喵神又去写H题去了。湛学姐又理论AC了一题,就是那个J题,枚举一下,套个高斯消元就过了啊。我用我的人脑评测机啊,测了测塔的算法,感觉确实没问题。D题、M题,早就会写了,我说:“你来写。”塔说:“我不写。这是码农题。传统码农题是讲代码量的,一题二百行。”我说:”那我来写。”这时候,我们等于呢,已经过了7题。喵神H一过,那就算过了8题了,啊。

喵神呢,交了两发H,然后发现题读错了。我说:”停停。没关系啊,我也读错了题。但现在,要以大局为重,让我写D和M。“我上去,一个手起键落,以迅雷不及掩耳之势,花了一个小时,才把,就把D和M写完了啊。我练过三、四年算法竞赛啊,训练有素。三小时的时间里,我们AC了6题。

喵神说H题过不了。我问,怎么回事,算法问题还是写法问题。塔说,算法和湛学姐讨论了,没有问题。一个DAG,点有点权,边有次数限制。从1点到n点,可以走无限趟,求最大价值。塔说,贪心,每趟取最大价值,不用写网络流。二十分钟就有人过了题啊。我一下没找出反例,说打印代码看看。

这时候啊,一个裁判,龙神,走了过来。他说,出题人,牟神,让喵神去写字符串。挑衅我们啊。我们哪有不理他的道理啊。既然这H题算法没问题,我说那我来看H题代码,你们去写E题字符串吧。塔们说,可以。

我拿过H题代码一看,没毛病啊。正着看,反着看,代码都倒背如流了,也没发现什么大问题啊。我用人脑编译器,诶,编译了一下,二进制代码都生成了,跑了样例,流程没问题,结果没问题。我啥也干不了了。

只听那边啊,谈论得,风生水起,什么后缀自动机、fail边,后来又是multiset,很复杂啊。我后缀自动机,都全忘,不能说全忘,都策略性地存储到了大脑深处了啊。没办法,很烦,帮不上忙。

最后半小时,没事干,我又看起了H题。突然,我想出了一组反例,嚯,算法假了。网络流带回边的,这样贪心表示不了操作撤销啊。最后也来不及想了,就也没过题了。

赛后一看,E题做法没错,F题也是会写,但没写。不算H题,理论上我们过了8题。四舍五入,其实就是一等奖队伍啊。最后,发现我们只有三等奖。其实,减去G题打印机导致的罚时,还是有二等奖的。但是出于对后辈的考虑啊,刻意没拿这个二等奖。

后来去问出题人,塔们说I题本来是A题,怕大家不敢看A和A调换了一下。塔们说是乱换的,塔们可不是乱换的啊。仔细反思,这次比赛,没有抢到更多的钱,原因有三点。一,签到题I题被替换了;二,打印机坏了;三,出题人挑衅参赛选手。这些出题人、裁判员,不讲武德,来,骗,来,偷袭,我们三个,加起来六十多岁的,老选手。这好么?这不好。我劝,这些出题人,耗子尾汁,好好反思,以后不要在题目顺序搞聪明,小聪明啊。

比赛结果,重要吗?不重要。重要的是你学会了什么,你得到了什么。比赛,要以和为贵,要讲娱乐,要讲友谊,不要搞,内卷化。谢谢朋友们!

总结

这次比赛,貌似是我生涯中结果最差的一次比赛。但是,这是非常有趣,令人难忘的一次比赛。不去追求名次,而是享受比赛本身,享受交流、合作、共同自闭,这是之前我从来没有做到的。很荣幸能参加这次比赛,能最后一次体会到算法竞赛合作的乐趣。

赛后仔细看了看榜,排名前列的好几个队都是大一队。正如其他人所说的,后生可畏,北理进Final有望了。但除此之外,我还有一些其他的期待:北理ACM集训队的寒假集训和暑假集训做的非常棒,通过大一一年的学习,有志于竞赛的同学能学到很多东西。但是,之后就没有什么正式的培养学生的流程了,很多情况下只能靠学生的自律来进行训练。ACM固然是强调个人能力的竞赛,个人能力是取得好成绩的前提条件。但是,个人的某些竞赛经验、思考方式是可以传承的,也有许多有潜力却没经验的人需要更好的指导才能成长。祝愿现役选手、未来即将加入集训队的同学们取得好的成绩。也希望你们在保证了自己的比赛成绩后,能把自己收获的东西传承下去,让北理的ACM水平一直提升。

最后打个广告,欢迎关注我的博客。我即将在一个月后对我的ACM经历进行回忆和整理,会发到博客和知乎。希望大家保持关注。

我对这篇文章的评论

文章以幽默的语气,生动形象地描写了老年选手在比赛时候的手足无措,同时其中透露出的欢快之情体现了选手享受比赛本身的放松心态,旨在让读者以一种全新的视角来看待算法竞赛。