仓库源文站点原文


title: 我的ACM脚印 date: 2020-12-21 01:31:14 categories: ACM&算法 tag:


2020年12月20日,南京区域赛结束,同时结束的,还有我的两年多的ACM生涯 接下来的寒假重心会向着找实习的方向努力,当然明年还有线下的区域赛、EC-finial以及明年的省赛等等,我都会去认真准备。

这篇文章会写什么

这篇文章更多的是想来自我总结一下历史,如果与你的理解有出入也请见谅

关于我

我的ACM简单的回顾

进入大学之前

我是2018年进入的大学,在这之前,我压根没有听说过ACM,也完全不知道这类竞赛,高中也是没有打过OI,也就是真正的纯粹的小白。当然,我的高中压根就不知道有什么叫OI的比赛,可能这就是所谓的省B类学校吧

但是我有优势,我从高一开始自学了程序,我当时想自己写游戏,然后学起来Unity了,也就顺便学了C#。至于优势,大概就是对程序有了自己的理解吧。如果让我对代码理解这个事情上进行一个分级的话,我会这样分:

而那时候的我,大概就是第三类的人,比起同时期的同学,只能说我拥有着非常好的起点

但是,实际上,通过一个学期的学习,基本上所有的学生都能到达这个水平

大一

大学的第一个学期,课程安排是学C语言,但是我其实并不需要,因为这些东西只需要我把我学C#的知识转成C就行了

而这个学期,校集训队也联系上了我,只不过因为我有提前的知识了,虽然我在那个时候还完全不知道对于代码还有第四层理解 当然,慢慢的我也接触到了很多算法,例如dfs、bfs之类的,只能说我在那个时候对ACM的理解还存在于ACM是提供更多的解决问题的办法而已 后来,学到了在ACM中最重要的东西:复杂度 也慢慢的开始学习到各种基础的算法:gcd、最短路、背包问题、KMP等等之类的

后来,我在大一快结束的时候,和另外两位大一参加了西安邀请赛,然后成功打铁…… 紧接着是校赛,但是那次校赛的难度太高,导致全场只有20个人过题,我有幸过了两题。但是我和之前组队的两个大一的同学分开了队伍。 然后是浙江省省赛,和两个大二的人组队,然后继续打铁 再接下来是南昌邀请赛,我终于拿到了人生以来的第一个奖牌:铜

然后就是整整一个暑假的集训,杭电的多校、牛客的多校,题目的难度对于当时我而言,未免是过高了一些。那两个月,可谓是绝对的自闭

大二

大二开始,大概是因为经历了暑假的自闭式训练,拿下了一个ICPC的区域赛银牌,虽然是银川偷鸡,但基本上是我一个人完成的比赛,而且其实本来很有希望冲击金牌

大二下半学期,因为疫情的原因,荒废了很久,没有出去打比赛,只能说是不断的学习吧。 也趁着疫情,顺便把CodeForces上把我的两个账号都刷到了紫名

当然,因为写的题多了,代码写的多了,感觉自己写题目的习惯开始发生了改变,特别是经常打CodeForces后,感觉自己对很多思维的理解在不断的加深。大一选择了图论方向,大二开始学数据结构,然后再学了字符串,稍微了解了dp,队内也把构造题的任务分配给了我

大三

这个学期难得有了好多场比赛,而我们原来参加了西安邀请赛的三个人,我们重新组成了完整的队伍,也夺下了省赛银牌、CCPC威海铜牌、ICPC南京银牌这样三个牌。

我的ACM成绩

到目前为止,总共拿下了两个ICPC区域赛银牌,一个CCPC的铜牌,一个浙江省省赛银牌,一个ICPC邀请赛铜牌,Codeforces两个账号都是紫名,准备寒假冲击橙名。接下来会参加一场线下的ICPC比赛以及EC-finial。未来可能在能够拿到offer的情况下,继续回来参加ACM竞赛

写给新人

ACM到底和数学建模、挑战杯等等的其他竞赛有什么区别

如果你是计算机学院的,那么你需要追求的、考虑的唯一的竞赛就是ACM

ACM是一个非常全面的竞赛,如果你说你只是喜欢数学,那么ACM比数学建模之类的数学竞赛更加具有挑战性,同样,难度更高。对的,在我的认知中,ACM对数学的要求甚至远远高于数学竞赛。因为ACM和其他比赛不一样的一点,便是ACM不设置任何的知识点上界,越新的知识点,越高级的知识点,ACM都可以考。甚至任何一道数学竞赛的题,如果你在ACM中见到,都是合情合理的。在打ACM的时候,这个知识点不会的情况是很正常的,是所有参加了ACM竞赛的人可以深切感受到的。而如果你只是去打数学之类的竞赛,如果你不能到达一个很高的层次,你可能很难体会到那种,自己完全不会,完全是毫无能力的那种绝望感。而在ACM,你可以在任何一场比赛中见到,甚至是随便在点开的一场比赛。

其次,ACM是一个非常公平、公正同时也是非常严格、残酷的比赛,甚至因为它的机制,你可以认为它是你整个大学生涯中见到过,最公平,也是唯一一个能够让参赛选手心服口服的比赛。因为ACM几乎不存在任何的主观因素,你只有准确完整的解决这个问题,你才能拿到那么一点成绩分。而且ACM系列竞赛结束,如果这场比赛有任何一道题有一些问题,通常出题人都会出面道歉。这也是我第一次知道,原来负责出题的人也是要道歉的。从那样的高考制度过来,我们甚至都不会去关心出题人是谁,即使他出了岔子,也会有专门的公关来解决。ACM却没有这些无聊的内容。

数学建模也好,挑战杯也罢,评委老师评分制意味着主观可以胜过客观,甚至,到最后可能变成了PPT大赛。如果说这类竞赛的好处,我觉得除了给你提高了拿到奖学金的可能性,对于自身能力的提升以及后续的工作而言甚至意义并不大。而奖学金,能比得上你找到一个好工作后在一个月内赚的钱多吗?你难道能一辈子拿奖学金过日子吗?当然这样的人是存在的,但是我相信大多数读者也和我一样,觉得这是一种奢望。

ACM到底带给我什么了

知识

我在ACM集训队的第一周,我所得到的知识,是我的室友们在大学四年内都可能会学不清楚、理不通的知识,而那些知识点,在我经历了两年多的ACM训练后觉得,这些只不过应该是理所当然会的、最基本的知识。这些知识点带给我的财富,是我在经历了四五个项目后,才意识到的我们与其他人的差距。ACM的知识点,只要你未来是做计算机行业的,那么它一定会在每一个角落里发挥着它的作用。

思维

ACM的题,对一个人的思维能力的提升有着非常恐怖的作用。特别是当你频繁的打Codeforces比赛时,你会深切的体会到自己的思维能力在以非常恐怖的速度进步。而与思维能力直接挂钩的,便是逻辑思路以及问题的敏感性。如果有人去看过杜老师的Codeforces录播视频,看过tourist的比赛视频,你会发现他们基本上并不会去论证一个方法的可行性,他们通常在读到这道题的时候,会反应过来这题“好像这样搞搞”、“在随便暴力一下”、“应该就对了”。这样的思路也正是我现在打Codeforces的一种感觉,当然我还不能到达杜老师这样对于这么难的题也可以如此轻松的想出解法,但是我仍然觉得我思考问题的思路和方向变得非常的开阔,而且思考问题的逻辑自然变得严谨合理。

代码实现能力

ACM的题,难度较高的题,有些需要各种数据结构的嵌套,需要各种开辟各种奇奇怪怪的数组。而你需要在短时间内完成代码的编写和调试,这无疑是对代码能力的直接挑战。例如Codeforces,5道题目只有两个小时,除掉读题(纯英文题面)和思考问题的时间,你又有多少时间可以来写代码调试代码呢?当室友还在为编译出错烦恼时,我们基本就不需要调试百行代码以下的程序,因为只需要简单的测试证明其确实没有错误即可。

ACM朋友圈

ACM届有一个最高级别的竞赛,被称为WF(world finial)——世界总决赛。这场比赛的含金量有多高?也许有人会说,最多也就是拿到金牌可以全球500强随意挑。但是,实际上只需要你碰到了这个比赛的边界,你只要有幸被邀请参加了这场比赛,不论你的名次,这个星球上的企业你已经可以随意选了,而且本科毕业就可以去工作的那种。而我们平时聊天水群,里面有的是因为ACM成绩优异而进入Google中国、微软亚洲研究院的人。而对于正常学业而言,各位也应该知道你需要读多少年的书才有胆量往这些企业中投递一份简历

学长学姐

通常能坚持下来打ACM的都是能够在思维、能力、勤奋或者智商上略胜一筹的人,那么和这样的学长学姐在同一个实验室的屋檐下打比赛,你能得到的帮助和支持,远远超过参加社团带来的收益。

直面清北复交

ACM竞赛是所有队伍在相同地点使用相同设备在相同的时间内解决相同的题目。

而你的对手则是来自全国的大学,对,北大清华每年都会来,而且非常重视。

ACM从来就没有院赛、校赛、省赛等等一大堆乱七八糟的东西,虽然他们确实存在但是他们并不是被官方承认的。ACM只有区域赛,(比如Asia-East东亚地区),区域总决赛(比如EC-finial,东亚地区总决赛),和世界总决赛(WF)。无论在哪个比赛,你都可能会遇到任何一个学校的队伍。所以在这样的比赛中,你可以很清楚的知道自己的水平在全地区范围内的位置,对自己的能力有一个更好的评估,能够看到外面更加广阔的天空。而不是拘泥于那么小的一个地区,争夺那么毫无意义的第一名

为什么要打ACM

因为我要证明我自己

在ACM比赛中,你会真实的,亲身和北大清华等等高校在同一个体育馆里,使用相同的设备相同的时间来解决相同的问题。那么你为什么不去证明自己比他们强?我知道这通常不可能,因为他们也会派出他们最强的队伍来与你们竞技。但是我们需要的就是在这么多的强队中,证明我们自己的能力。在计算机领域内最有影响力的比赛中,证明自己而已

什么样的人适合去打ACM,什么样的人不适合去打ACM

ACM竞赛是一个需要大量的时间去投入,但是到很久之后才会有结果的产出。这和其他竞赛不同,数学建模通常你只需要很短的时间训练就能拿出成绩,而一个ACMer,在大三之前甚至可能都没有一点点成果。但是你在大一大二的投入终将会给你在大二下至大三上的时候带来丰富的回报。

这样的回报,需要愿意投资的人耐心投资才有可能赚得盆满钵满,一旦出现懈怠都有可能颗粒无收。耐心、专注、勤奋、自觉这些是一个ACMer必须要具备的因素。

写给已经进入了ACM的人

我在ACM的训练计划

除了ACM之外的计划

ACM毕竟只是我们大学的一个工具,我们希望它能够服务于我们找工作、服务于我们在其他领域的发展。不可以把ACM当成是自己在大学里唯一执着的对象,甚至把它树立为人生目标,这不合实际也没有意义,反而会影响你的正常社交与生活,这不应该是一个人的目标。

关于ACM写题

ACM算法的学习规划

在经历了两年多的学习之后我发现,其实很多的算法并没有太多的学习意义,或者说不必要为其投入过多的经历去学习。 我是负责队伍内的图论+字符串,以及构造题思维题,会数据结构,了解dp和树上问题。 另外一位队友负责计算几何和博弈论,以及数论,会dp,了解图论和树上问题 还有一位队友负责了数据结构和dp,以及树上问题,会数论,了解图论 基本上可以说是覆盖了所有的知识面,而且大部分知识面都是有多个人会。

我以我熟悉的图论为例,诸如“最大流”这些个算法,通常对于一个银牌队伍而言,其实学习的意义并不大。因为我至今未见到过最大流题的难度低于金牌题的(按照实际区域赛出题情况)相反,灵活的结合思维和拓扑排序,你会发现图论问题变得非常简单。很多区域赛的图论的铜牌题在你眼里变成了暴力傻逼题。这是对于一个图论选手在频繁使用图论相关的知识点的时候自然而然形成的。

我认为把学习那些过高的知识点重要性低于去熟练掌握最基本的算法的内容。

对于字符串也一样,上一次看到“回文树”是在复现赛上看到的,是一道金牌题,虽然对于会“回文树”的队伍而言相对简单很多,但是作为一道金牌题,很多时候在比赛现场可能根本没有时间去看这样一道题。

当然你的队伍是为了冲金牌的,这些知识点当然也应该成为你的必须知识点之一。

我的一些经验之谈

Shiroha @2020.12.21凌晨1点30分