1. 为什么CodeM能吸引这么多人去打以及复赛到底考什么1.1 参赛动机与赛事初印象2017年那会儿算法竞赛圈子里的氛围和现在不太一样。ICPC区域赛一年就那么几场能进现场赛的队伍名额有限很多认真刷题的同学一年下来也难有几次正式比赛的实战机会。所以当CodeM这种由大厂主办、线上初赛海选、线下复赛现场比拼的赛制一放出来圈子里讨论度非常高。CodeM是美团那个时期主打的编程大赛品牌全称大概可以理解成Code-M核心就是通过算法题筛选真正有工程和算法底子的选手。2017年这届规模和赛制都比较成熟初赛报名人数很多复赛是优中选优能走到这一轮的人水平已经相当不错了。我当时参赛的动机其实很简单一个是想检验一下自己连续刷了半年题之后的真实水平另一个是想通过比赛看看业界到底需要什么样的算法能力。毕竟平时在学校里做题题目本身是老师或者教练挑好的题型相对固定和真实竞赛里那种题目风格混杂、难度曲线诡异的场次还是有区别。1.2 赛制与复赛门槛CodeM 2017的赛制大致是初赛若干轮每轮若干题按排名晋级最后到北京参加复赛。复赛是现场赛机考形式时长一般在三到五小时之间题量大概是五题左右。这个题量和ICPC的五个小时十题比起来不算多但每道题的设计密度很高不是说暴力一下就能过的。复赛的门槛在于初赛排名筛选了一大批人能进复赛的基本都是能在限时内稳定做出中等难度以上题目的选手。到了这个层级比拼的已经不再是会不会某个算法而是几个更现实的问题面对一道从没见过的题能不能快速找到正确的模型转化在多个题之间如何分配时间代码实现的时候能不能一遍写对不因为边界条件反复调试浪费时间。这些能力靠临时抱佛脚是补不上的。2. 复赛题目风格与考点分布复盘2.1 题目类型概览按照我的赛后复盘复赛的题大致可以分成三类。第一类是数据结构题核心考点是树状数组、线段树这些常见结构但一般会套一个比较隐蔽的操作需要你先对原始问题做一些转化才能套上数据结构。第二类是动态规划但绝不是普通的背包或者区间DP而是带着状态压缩、矩阵快速幂这类进阶技巧的题目有些题甚至需要你先从题目描述里抽象出一个自动机模型再做DP。第三类是思维构造题这类题最考验临场感觉有时候解法本身只需要几行代码但如果想不出那个关键结论就是死活做不出来。这三种类型的分布不是平均的通常情况下动态规划和数据结构各占一到两题构造题至少一题剩下的位置可能是图论或者数学题。这个比例其实反映了当时互联网公司算法比赛的一种倾向比起纯粹的数论技巧更看重你把问题抽象成模型并用代码实现的能力因为这种能力最贴近实际业务里的需求拆解。2.2 为什么这些题会成为复赛的主流题型这里我想多说一点因为理解出题人的意图对参赛是有帮助的。动态规划和数据结构考得多的直接原因是这两种题型的区分度最好。一个选手是真正理解算法的本质还是只会套模板遇到需要做一层转化才能下手的题时立刻就能看出来。举个例子如果一道题直接告诉你求区间最大值那会写线段树的人都能过区分不出水平。但比赛题不会这么直接。它可能会给你一个序列和一堆操作每个操作是区间翻转之后查某个位置的值这时候你就得自己想到用平衡树或者用分块加懒标记不同的解法有不同的复杂度和实现成本最终体现的是选手对问题本质的理解深度。另外这类题目还有一个特点就是题目描述往往是面向实际业务场景包装过的。2023年前后的比赛题尤其明显描述里会出现某个外卖订单序列用户访问日志优惠券使用规则这类词但剥掉壳子之后核心还是经典的算法问题。这种包装方式就是为了考察选手是不是能从具体的业务描述中抽象出数学模型这和大厂日常工作中做的事是一样的。3. 最具代表性的题型动态规划与状态压缩3.1 一类典型状态设计题的完整推导我至今记得复赛有一道题大概意思是说有一个长度为n的序列每个位置有个值你需要进行若干次操作每次操作可以把一段连续区间的值全部加一或者全部减一求让整个序列变成非递减序列的最小操作次数。这道题表面上像是在考区间修改和贪心实际上核心是一个动态规划。我第一次读完题的时候也在想是不是能用差分数组加贪心直接做但推了一下发现不行因为区间的操作是可以叠加的而且目标不是变成全相等而是非递减这个条件让贪心策略变得非常不稳固。正确的思路是把原问题转化成另一个等价问题设最终需要修改的总次数为x那么每个位置的修改次数可以拆成两个部分一部分来自使它比前一个位置大而额外增加的修改另一部分来自维持它不比后一个位置小所需要的调整。这个转化本质上是在说我们不需要真的去模拟哪一段区间被加了几次只需要关心相邻两个位置的相对变化量。于是可以设计一个DP状态用dp[i][j]表示前i个位置处理完并且第i个位置被j次操作影响过的最小总操作次数。j的取值范围就是操作次数的可能区间。这个状态复杂度看起来是O(n*m)的m是操作次数的上界但因为每次转移只依赖相邻位置之间的高度差所以可以用前缀最小值优化。我当时写了大概四十行代码核心转移就一个公式dp[i][j] min(dp[i-1][k] max(0, a[i] j - a[i-1] - k))其中k是上一个位置的操作次数。这个max(0, x)的含义是如果当前这个位置即使加了j次之后仍然小于前一个位置加了k次之后的值那我们就不得不额外补上差值这就是需要的新增操作次数。3.2 代码实现层面的几个关键细节代码写起来有几个坑我在这里提醒一下。第一j和k的枚举范围如果直接开两层循环再加上一个内部min操作最坏情况下会达到O(nm²)m如果到了几千就彻底超时了。所以一定要用前缀最小值去优化掉内层那个min的枚举转移就变成了O(nm)。我当时第一次实现的时候没有意识到这一点直接写了三层循环本地测试小数据没问题一上大数据就卡死后来才反应过来要优化。第二上界m怎么定。如果你根据数据范围猜一个很大的数比如十万那DP数组会直接爆炸。实际的做法是先做一次贪心求一个可行解然后以这个可行解的操作次数作为上界因为最优解一定不会比任一可行解更差所以这个上界是安全的。我当时先用一个简单的差分贪心算了一个初解再把这个值作为DP的上界这样复杂度就完全可控了。第三注意long long。我当时被这个坑过一次因为操作次数乘上序列长度之后的数据范围很容易超过int不用long long就会在最后几个样例上WA。比赛的时候一定要在一开始就把所有涉及累加计数的变量都声明成long long不要等到出错了再改那样很浪费时间。再补充一个判断技巧如果一道题目关键约束出现在区间修改和最终状态需满足某个性质上十有八九可以往差分和DP这两个方向想。区间修改本身不是重点重点是每一次修改对相邻位置关系的影响这个视角一旦切换过来很多题都会豁然开朗。4. 复赛现场的时间分配与工具准备4.1 我的做题节奏和决策逻辑现场赛和在家里刷题最大的不同点是一旦进入比赛状态时间流逝的速度感知会明显失真。特别是当你盯着一道题想不出来的时候二十分钟就像两分钟一样过去了。所以时间分配不能靠感觉赛前就得有一个粗略的计划。我的策略是把五道题从头到尾读一遍大概花十到十五分钟快速判断每道题的题型和难度然后给每一道题打一个标签能做、可尝试、需要再看看。之后从自己最有把握的题开始写。很多人喜欢按题目顺序做题认为前面的题简单后面的题难这种想法在正规比赛中基本不成立题目的难度和题号没有必然关系。我当时就是因为按顺序做卡在第一题上浪费了太久导致后面时间不够这个教训后来每次比赛都会提醒自己。第二个策略是设定单题瓶颈时间。我给自己定的规则是一道题如果超过四十分钟还没有完整的可行思路就立刻放下去做下一道。因为如果思路是对的四十分钟足够写出一个能跑的版本了即使有小bug也说明你已经走在了正确的路上。反过来四十分钟还没思路说明这个题的方向大概率想偏了继续耗下去也不会有什么进展不如先去做其他题稳住基本盘。4.2 本地环境的配置与常用模板清单比赛用的机器一般都不太熟悉系统环境、编辑器、编译器版本都可能和平时不一样这个不确定性会额外消耗时间。我的习惯是准备一个移动环境里面放好自己常用的配置文件和模板代码进场之后先花五分钟把环境调到自己顺手的状态再开始看题。模板代码不需要准备得特别花哨但几个常用的东西一定要有。快速读入的模板是必须的特别是当数据规模大的时候用cin不关同步流会慢很多。我自己会准备一个通用的快读模板处理int和long long的输入。然后是常用数据结构的模板线段树、树状数组、并查集、最短路这些基础结构我都是背下来的但会提前写好放在代码库里需要的时候直接复制粘贴改一改就行不用现场从头敲。还有一点容易被忽略现场赛的机器上可能没有你平时用的代码片段管理工具所有模板都得靠记忆或者U盘带进去。U盘这个东西不同赛事的规则不一样有的允许有的不允许。所以最重要的还是把常用的模板结构背熟不要依赖外部工具。我自己的经验是模板只要用过十次以上基本就能条件反射地敲出来根本不用刻意背。5. 全场最容易踩的坑读题、精度与边界5.1 读题陷阱与样例之外的隐藏条件有一类题样例给得非常简单小到你可以直接手算验证但真正的大数据里隐藏着很多你没注意到的边界。最典型的就是数组下标从1开始还是从0开始的问题。如果你习惯了从0开始而题目的描述里大量使用的是1-based的说法写着写着就很容易出现差一错误。这种错在本地小数据很难发现因为小数据即使偏了一位结果也可能碰巧是对的。我自己在复赛时就因为读题不够仔细把一个区间内不同数字的个数理解成了区间内所有数字的和白白浪费了半个多小时在一个完全错误的方向上。后来重新读题才发现题目问的是distinct count不是sum。所以读题这件事宁可多读两遍也不要急着动手。我的一个个人习惯是读完第一遍题干之后用嘴把题目的意思复述一遍如果发现自己说不清楚某个细节那就是还没读懂需要再看一遍。另一个经典陷阱是数据范围里可能为负或者可能为0这种隐藏条件。很多人在设计算法的时候只考虑了正数的情况结果负数一进来整个贪心或者DP的初值设置全部变得没有意义。所以在动手之前把每一个变量的取值范围写清楚尤其是下界是不是0上界会不会超过int这些都要提前确认。5.2 浮点精度与常数优化问题有一道题我在现场一直卡在精度上怎么调都过不了。后来复盘的时候才意识到问题出在我把中间结果先除了再判断导致误差被放大。正确的做法是把除法改成乘法比较比如判断a/b是否大于c可以直接判断a是否大于b*c前提是b和c都是正数。这个改动看似微小但能显著减少浮点误差。浮点问题的另一个常见来源是double的精度不够。当数据范围达到1e9甚至更高的时候double的尾数精度就只有大约15位有效数字如果你在中间步骤进行了很多次乘法运算精度很快就会不够用。这时候要么改用long double要么用整数运算代替浮点运算。我倾向于后者因为整数运算不仅零误差而且速度也更快。常数优化也是一个值得提前想清楚的点。比赛里经常遇到的情况是你的算法复杂度理论上是能过的但因为常数太大实际运行超时。比如线段树如果递归深度太深或者用了大量的vector和pair运行速度会明显下降。我自己写线段树的时候习惯默认使用数组模拟二叉树的形式也就是下标2i和2i1这样可以避免显式定义左右儿子指针也能利用内存连续性加快访问速度。超时排查的具体方法我一般是先看数据规模估算理论上的运算次数。如果估算出来是1e8次左右那运行时间大概在1到2秒之间这种情况下常数优化就很关键。这时候我会检查代码里有没有大量动态申请内存的地方有没有不必要的排序有没有重复计算。很多时候一个简单的记忆化数组就能把复杂度降下来。6. 赛后复盘哪些能力在复赛中最值钱6.1 各题得分率与我的策略评估赛后我按照自己的记忆复盘了每道题的表现。数据结构题因为平时刷得比较多完成得比较顺利这得益于我在赛前总结过一套经典数据结构的模板库包括基于数组的线段树、树状数组、动态开点线段树以及能用bitset优化的状态压缩类题目。动态规划题花的时间最久最后在边界处理上还出了点问题说明我对DP的熟练程度还有提升空间。构造题基本上没有头绪只骗到了一点部分分这个结果其实符合我平时的训练情况因为构造题确实做得少。从策略上看整体还算成功因为我坚持了先易后难的原则没有在难题上死磕太长时间保证了基础题的分数。如果当时一上来就对着构造题较劲很可能基础题的分数都拿不全最终排名会更难看。不过策略上也有一个明显的失误我在第一道数据结构的题上虽然AC了但写完之后的验证过于简单只测了样例和几组自己构造的小数据没有仔细检查极端情况比如空序列、全相等的序列、很大的数。这几类边界情况恰恰是最容易出bug的地方以后不管是一场练习赛还是正式比赛写完一道题之后都应该先专门针对边界数据自测一遍再提交。6.2 给下一届参赛者的几条建议如果你准备参加下一届CodeM或者类似的大厂算法竞赛我有几条很具体的建议。一个是平时训练的时候要有意识地模拟比赛环境而不是一直处于刷题模式。刷题模式里你做不出来可以马上看题解可以慢慢想但比赛不会给你这样的条件。模拟比赛的时候给自己设定严格的时间限制用真实的复杂度标准来要求自己甚至可以用一个倒计时软件到点必须交卷。只有长期在这种高压状态下练习比赛的时候才能真正发挥出平时训练的水平。另一个是加强构造题和思维题的训练。很多人把精力全部放在数据结构和动态规划上觉得构造题靠天赋不值得刻意练但实际上构造题也有套路可循。常见的方法包括打表找规律、从极端情况入手、利用对称性和二进制分解等。建议每周专门找几道构造题来练习不用多但要坚持。最后一点是关于心态管理。比赛过程中情绪波动是非常正常的尤其是当你看到别人已经把某道题AC了而自己还没有思路的时候焦虑感会非常强烈。这种时候我的应对办法是刻意地看一眼时间然后告诉自己我现在只需要专注于自己面前的题别人怎么样跟我没关系。这个自我暗示虽然简单但在高压场景下真的管用。CodeM 2017复赛对我来说是一次非常宝贵的实战经历。它让我清楚地看到了自己在算法能力上的优势和短板也让我对竞赛和工程实践之间的关系有了更深的理解。如果你也想参加类似的比赛我的建议是把它当成一次学习机会而不是单纯的名次角逐。每一道你卡住然后又终于解出来的题都是一次高质量的思维训练。赛后及时复盘比多做十道新题还管用。
