CodeM复赛经验分享：算法竞赛备赛策略与实战技巧

2017年夏天我坐在北京一间闷热的出租屋里盯着屏幕上 CodeM 美团编程大赛复赛的倒计时手心全是汗。那是我第一次认真对待一场由互联网公司主办的编程竞赛也是我第一次意识到算法题不是刷得多就一定能赢更考验的是在有限时间内对问题本质的判断力。CodeM 是美团点评主办的面向开发者的编程竞赛赛程分为初赛、复赛和决赛复赛从数千名选手中筛选出晋级者。相比很多纯 ACM 风格的比赛CodeM 的题目更贴近工程场景很多题面会包装成外卖调度、商家评分、路径规划之类业务背景但核心还是算法与数据结构。对我这种平时写业务代码、周末才刷题的人来说复赛是一场从会做题到会比赛的跨越。这篇文章不打算复述某道具体题目的标准解法那在官方题解里都查得到。我更想聊聊这一路踩过的坑、总结出的节奏以及复盘时发现的那些本来能拿分却丢了的瞬间。如果你准备参加下一届 CodeM或者任何类似的算法竞赛这篇文章应该能帮你少走一些弯路。1. 复赛前三个月我重新定义了备战1.1 先盘点自己的知识体系别急着刷题很多人备战算法竞赛的第一反应是打开题库每天刷三五道但刷了一个月发现会的还是会不会的还是不会。我的教训是备战开始前先花两天时间把自己的知识盲区列出来。我把算法知识分成几个大块基础数据结构栈、队列、链表、堆、并查集、高级数据结构线段树、树状数组、平衡树、图论最短路、最小生成树、网络流、动态规划背包、区间、状压、数位、字符串KMP、字典树、后缀数组、数论GCD、素数判定、欧拉函数、组合数学、计算几何和搜索。然后对着 CodeM 往届题目回忆如果某个知识点我连题解都看不明白就把它标记为重点补强。这个过程很枯燥但非常必要。因为复赛只有几个小时你不可能在考场上现学一个数据结构。提前摸清自己的底牌才能把有限的备战时间花在刀刃上。1.2 刷题质大于量每道题至少要复盘两遍我见过一些选手一天刷十道水题看起来很努力但比赛时遇到变形题照样懵。我的备战方法是每天认真做两到四道题每道题做完之后必须做三件事看官方题解或高票题解、对比自己的思路差距、关了题解重新写一遍。这个重写一遍非常关键。很多时候你以为自己会了实际只是记住了代码并没有真正理解为什么这么做。尤其是动态规划的转移方程看题解时觉得原来是这样但合上屏幕自己推一遍经常会卡在状态定义上。CodeM 复赛这种级别的比赛考的就是你自己推到那一步的能力。另外一定要用虚拟参赛的方式模拟真实比赛。找一套往年的复赛题定好时间关掉聊天工具像正式比赛一样做满三个小时。我第一次虚拟参赛时两个小时就坐不住了总想看一眼手机。这种专注力训练比多刷二十道题都管用。1.3 参加比赛的硬实力手速、模板与容错算法竞赛不仅是智力游戏也是手速游戏。同样一道题别人十分钟打完你磨了半小时差距就出来了。我赛前把常用的代码模板整理了一份包括快读、并查集、线段树、最短路、KMP 等提前背到肌肉记忆里。不过模板只是起点更关键的是容错能力。CodeM 的题目往往有大量边界条件比如数组下标从 0 开始还是从 1 开始数据范围是否爆 int图是否可能不连通。我赛前定了一个规矩每道题提交之前先检查三遍边界确认没有平行数组、没有下标越界、没有把 n 和 m 写反。这个习惯帮我避免了好几次无谓的罚时。2. 复赛当天的做题策略先通读再动手后死磕2.1 拿到题目的前十五分钟我只做一件事读题复赛的题量一般是四到六道难度递增但第一题往往不会是纯签到题也可能有陷阱。很多人一上来就盯着第一题开始码结果码到一半发现题意理解错了白白浪费半小时。我的策略是前十五分钟把所有题目全部读一遍用一句话在草稿纸上概括每道题要求什么、数据范围多大、预计用什么算法。这样做有两个好处一是避免在难题上浪费过多时间二是方便规划做题顺序。比如有一道题数据范围是 n 小于等于 10那大概率是状压 DP 或者暴力搜索如果 n 小于等于 10 万那得考虑排序、二分、贪心或者数据结构优化如果模数是素数且要求组合数那就是数论题。读题阶段把这些预判写在纸上后面做题时思路会清晰得多。2.2 按得分性价比而不是题目顺序做题CodeM 复赛的赛制通常是罚时赛也就是说提交错误的代价是时间惩罚。最忌讳的是死磕一道难题磕了一小时没磕出来结果后面几道能拿分的题没时间写。我给自己定了一个简单的评估公式先估计每道题的难度和预估得分然后优先做预计用时短且得分高的题目。一般来说第一、二题是保底题必须拿下第三题是中等偏上的题视情况投入第四、五题如果有思路就试试没思路就写暴力拿部分分。这里要特别强调部分分的价值。很多选手觉得自己不会正解暴力分就不写了直接放弃。实际上CodeM 这类比赛的数据通常是分档的即使是暴力解也能拿到 20% 到 40% 的分数。如果你能在一道正解做不出来的题上稳扎稳打地写个暴力那你的总排名会比直接放弃的人高一截。2.3 题型分布与应对策略从业务包装里抽离出数学本质CodeM 的题目有一个很明显的特点喜欢用业务场景包装算法内核。比如外卖骑手的最优路线是图论最短路商家评分排序是数据结构优惠券组合是动态规划。这种包装虽然让题目看起来更实际但如果被业务故事带偏就容易忽略真正的数学模型。我的处理方法是读题时先跳过背景故事直接看输入输出和数据范围。通过输入输出反推这道题在问什么数学问题。比如看到求最大值的最小值那十有八九是二分答案看到求方案数那多半是 DP 或者组合数看到求最小生成树就找边权和连通性条件。这种去故事化的能力需要平时刻意训练。我建议备战阶段做往年题时每道题先不说话先读题十秒然后自己在纸上写下这题考的是 XX 算法再继续做。坚持一个月读题速度会明显提升。2.4 时间分配前一个小时决定心态最后一个小时决定排名我观察过一个规律很多选手在比赛前半段表现不错但做到中段遇到一道卡壳的题心态就崩了后面几道题也发挥失常。为了应对这种情况我给自己设定了三阶段时间计划。第一个小时主攻前两题目标是全部拿下。即使有一题卡住了也不要恋战最多花四十分钟如果还不行立刻切到下一题。第二个小时做第三题和暴力分这两部分决定你是普通人还是高手。第三个小时回过来死磕前面卡住的题同时花五分钟检查已提交的代码有没有低级错误。最后那十分钟不管有没有做出来都要停下来把所有已提交的题的代码重新读一遍检查数组大小、变量类型、循环边界。这个习惯意外地救过我一次让我在最后一刻发现并修正了一个变量作用域的错误。3. 那些让我丢分的经典大坑赛后的忏悔录3.1 读题不仔细是我复赛里最大的失误复赛的时候我做一道关于字符串编辑距离的题题目里说得清清楚楚只允许插入和删除两种操作不允许替换。我脑海里条件反射地认为是标准的三种操作于是按编辑距离写了动态规划样例过了提交却 WA 了。当时的我完全蒙了翻来覆去检查了十几分钟后来才重新逐字读题发现问题出在操作定义上。这种失误的本质是我把刷题经验当成了题意本身没有尊重题面里的每一个限定词。从此以后我给自己立了一条规矩读题时把只有必须不能任意连续这类词圈出来写代码之前再回看一遍。别以为这是废话CodeM 这类比赛故意在限定词上挖坑是常态。3.2 int 溢出和数组越界代码的隐形杀手另一道让我印象深刻的题是一道求前缀和最大值的题。数据范围看起来不大n 是 10 万每个数不超过 10 万但前缀和累加之后可能达到 10 的 10 次方远超 int 的范围。我当时用的语言是 C顺手写了 int结果一提交就 WA。其实这类低级错误完全可以通过估算中间结果范围来避免。我在赛后复盘时给自己列了一张清单凡是涉及累加、乘法、组合数的题目一律至少用 long long凡是数组下标必须确认是否会访问到 -1 或者 n 的位置凡是递归函数必须确认深度是否可能超过栈限制。这张清单在后来的比赛中救了我很多次。比如有一次一题要求模运算我在减法后忘记加模数导致结果变成负数就在提交前用清单检查出来了。3.3 暴力解法的价值拿不到正解也要拿部分分复赛有一道图论题要求找给定起点到所有点的最短路之和。数据范围很大直 Dijkstra 肯定超时我的正解思路是建反图加拓扑但当时越想越乱代码写了一半写不下去。按照我三阶段的时间计划我果断弃掉正解转而在剩余时间里写了一个朴素 BFS 的暴力版本虽然只能过小数据但按照数据分档的设计还是拿到了大约三成的分数。这一下就把我的排名拉回了中游偏上的位置。赛后我常跟朋友说竞赛不是造火箭而是抓分。你不可能每道题都满分但你完全可以保证自己该拿的分一分不丢。所谓该拿的分就是暴力分、部分分、签到分。把这些抓稳了你的排名一定不会差。3.4 心态崩盘时的自救办法离开屏幕一分钟很多人低估了心理因素对比赛的影响。复赛进行到中段时我有一道卡了很久的题提交一次 WA 一次眼看着时间一分一秒过去心脏砰砰跳脑子一片空白连最简单的代码都写不利索了。后来我强制自己站起来去倒了一杯水盯着窗外看了一分钟什么也没想。回来之后我重新读了一遍题面竟然发现之前的思路漏掉了一个重要条件。那一刻我才明白冷静下来比任何技巧都重要。所以在比赛时如果连续三次提交都错不要继续盲目修改先停下来深吸一口气换个角度重新分析。很多问题不是因为你不会而是因为你太着急被再试一次的惯性带着走。4. 复赛之后的复盘从比赛结束到能力真正提升4.1 先交卷再补题复盘比比赛本身更重要比赛结束的那一刻很多人的第一反应是去对答案、问别人做对了没有。我的建议是先别急着对答案趁热把每一道题重新做一遍尽量在几天内补完。补题的时候不要看题解先自己独立地想十分钟。想得出来就想想不出来再看题解但看完之后必须合上题解自己完整地写一遍并跑通所有样例和自测数据。这个过程是痛苦的但它能把一次比赛的经验真正内化成你的能力。我复赛结束后有四道题只完整做出来两道另两道靠暴力拿了一点分。复盘时我花了一周时间把四道题全部重写并整理到自己的错题本里。半年后我再回头看这些题发现当初觉得毫无思路的题目现在已经能一眼看出考点这就是复盘带来的成长。4.2 跟高手学思路看高排名的代码是一面镜子CodeM 赛后开放了代码查看至少在当时的赛事交流社区里可以看到部分选手的提交。我去看了排名靠前的选手的解题代码深受震撼他们的代码非常简洁没有多余的变量没有花哨的装饰甚至有时候连注释都没有但结构极其清晰。相比之下我写代码喜欢加很多不必要的封装和冗余判断表面上是为了稳妥实际上是思路不够清晰用堆代码来弥补逻辑上的模糊。从高手的代码里我学到了一个重要的原则先用伪代码把思路在纸上理清再动手写正式代码。如果你的手在写代码时还在犹豫下一步该做什么说明思路还没理顺停下来重新想。4.3 算法能力之外的隐性收获工程思维的打磨CodeM 和纯 ACM 比赛还有一个不同点它的题目更强调用算法解决实际场景中的问题。虽然比赛时我们关心的是算法复杂度但赛后仔细想想这些思路对日常开发也很有启发。比如有一道关于外卖订单调度的题本质是如何在不超载的前提下最大化配送效率这其实就是一个简化版的负载均衡问题。再有像商家评分统计的题底层是区间查询和排序和业务里的排行榜功能几乎一一对应。参加完复赛之后我回头看自己平时写的业务代码发现遇到性能瓶颈时第一反应不再是无脑加缓存而是先分析数据规模和算法复杂度这算是比赛带给我的隐形财富。5. 如果你也想尝试 CodeM给下一届选手的实用建议5.1 提前熟悉竞赛平台和软硬件环境很多人第一次参赛连编译选项、文件读写方式、内存限制都没弄清楚结果开场就慌了。CodeM 使用的是在线评测系统你只需要提交代码不需要处理文件输入输出但不同语言的时间和内存限制不同赛前最好用往届题目演练一遍确认自己的语言版本是否支持某些语法特性。比如在 C 里有些老版本编译器不支持__int128有些环境没有开启-stdc17如果你在代码里用了这些特性就会出现本机能过、评测机 CE的悲剧。建议在比赛前用平台提供的测试功能提交一段极简代码确认环境没问题。5.2 积累一套属于自己的板子不是抄板子网上有很多算法模板库但直接照抄在考场上并不好用因为你根本不理解每一行在干什么遇到变形就懵了。我建议你自己手写一套常用算法模板比如快读、并查集带路径压缩和按秩合并、最小生成树Kruskal 和 Prim、最短路Dijkstra 和 SPFA、线段树区间加、区间求和、树状数组、KMP、字典树、快速幂和组合数。手写模板的过程其实就是在考前把每个算法的细节过一遍。比如并查集路径压缩的递归写法在数据大时可能爆栈我就会改用迭代写法比如线段树的数组要开四倍空间这个四倍是为什么我也要心里有数。只有自己写过、踩过坑考场上才能用得很稳。5.3 刷题时带着比赛感去刷而不是纯刷题我见过很多备战者刷题时做一道看一道题解做不出来就立刻打开题解然后觉得自己懂了下一道题又不会。这种刷题方法效率很低因为它缺少了独立思考-试错-放弃或突破的完整循环。我在赛前一个月特意调整了刷题方式每次打开一套模拟题先设定一个时间限制比如每题半小时在限制内完全独立思考实在做不出来再去看题解。看题解之后必须把这道题收藏起来三天之后再独立做一遍。这样做一遍题比无脑刷十道题都有用。5.4 保持休息别把身体熬垮听起来是老生常谈但复赛当天真的有选手因为前一天熬夜刷题在考场上困得连题都读不进去。竞赛比拼的是脑力而脑力的基础是充沛的精力。赛前一周就要开始调整作息尽量让大脑在比赛时间段保持兴奋。另外比赛前少吃太油腻的东西不然血液都跑到胃里去了脑子缺血。虽然我这话说得有点养生但亲身经历告诉我白天比赛时昏昏欲睡的那种绝望比做不出题还难受。6. 写在最后CodeM 复赛到底给了我什么现在回头看CodeM 复赛的名次其实已经模糊了但那段经历留下的东西却一直还在。它让我第一次系统地梳理了自己的算法知识体系让我学会了在压力下冷静分析问题也让我明白了比赛不仅仅是做题。如果你问我该不该报名这类比赛我的答案一定是报。不要担心自己水平不够也不要怕丢脸。算法竞赛的价值从来不只是那一张获奖证书而是在备赛、比赛、复盘的过程中你逼着自己把一个又一个模糊的概念彻底搞懂这种被大赛倒逼着成长的体验是平时工作里很少能获得的。最后再分享一个我到现在还在用的小技巧每次刷完题无论做对做错都在题目旁边写一句话——这题考了什么下次遇到怎么识别。别小看这句话半年之后当你积累了上百条这样的注释再回头看你会发现自己真的会做题了。