1. 一场线上算法赛为什么值得拿出来说CodeM 2017美团编程大赛是我打过的线上算法赛里印象比较深的一场。那会儿算法竞赛圈子里大家主要都在刷ACM题、打Codeforces企业办的大型编程比赛还没有现在这么多。美团在这时候搞了个CodeM初赛分A轮和B轮B轮的时间我记得很清楚——2017年6月的一个晚上晚上7点到9点两个小时线上答题。当时抱着试一试的心态报了名结果这一场打下来我对“企业出的算法题”和“ACM出的算法题”之间的差别有了很直观的感受。这篇文章不是官方复盘就是一个普通参赛者根据自己的参赛经历、赛后查到的题解、以及在本地重新实现验证后整理出来的内容。适合三类人看一是对算法竞赛有兴趣、想了解企业编程大赛是什么画风的学生二是准备参加类似线上笔试、想提前感受美团风格题目的求职者三是纯粹想看看几道中高难度算法题怎么一步步拆解的算法爱好者。可以先把结论放在这里CodeM初赛B轮的题目整体难度是“两道签到 两道需要想一会儿的中档题 一道硬骨头”的结构。和前一轮的A卷相比B轮的思维量明显更大代码量倒没有特别夸张。更像是在考你“能不能把一个业务问题抽象成算法模型”而不是纯粹比谁模板背得熟。2. 比赛整体思路与赛制拆解2.1 赛制与晋级规则CodeM 2017的赛制大致是先线上资格赛然后初赛分A、B两轮两轮都参加的话取成绩更好的一轮来算晋级名额之后是复赛最后是线下决赛。初赛B轮就是整个晋级链路里的第二场。每场持续两小时用官方自研的在线评测系统提交代码支持C/C、Java、Python等主流语言。比赛时能看到实时排名提交结果会立刻反馈每道题都有通过率统计。这赛制放在今天看不算稀罕但在2017年企业自己搭建评测系统办比赛还是一件挺有魄力的事。它和传统ACM赛制最大的区别在于ACM通常是一台机器五小时做十道题拼的是全面性和耐力CodeM这种线上赛更接近求职笔试每道题覆盖一个方向整体难度曲线就是用来筛人的。初赛B轮里题目从签到题到压轴题分布得非常典型实际上是在模拟工程师日常工作中从“基本功”到“复杂系统设计”的梯度。从参赛策略上讲这种比赛最忌讳的就是一上来猛磕压轴题。我看到有同场选手前30分钟全花在第四题上结果中间几道能拿分的题没时间写。正确做法是先快速扫一遍所有题目把送分题稳稳收下然后按自己擅长的方向逐题突破最后剩余时间再用来挑战硬骨头。2.2 题目风格从业务场景抽象出来的算法模型B轮给我印象最深的一点是题目里带着美团业务的影子。线上赛的题目并不是那种纯数学背景的抽象题而是把实际业务场景做了一层“算法化包装”。比如订单、配送、红包、优惠券这些美团的核心业务概念都会在题面里出现。但剥掉外壳之后内核还是经典的数据结构和算法。这也是企业编程大赛和ACM最不一样的地方。ACM题目追求的是纯粹的抽象和较深的理论模型往往题目背景只是一个故事甚至故事完全不相关。而CodeM的题目能看出来是业务团队或者算法团队出的他们在设计题目的时候会有意识地往自己的业务场景上靠让选手在解题过程中感受到“我是在解决一个真实世界的问题”。这种风格对选手的要求其实更高。因为你不仅要有算法功底还要能从一段描述得比较接近产品需求的题面里快速提取出真正要算的东西。我后来在面试时发现这种能力在真实工作中很重要——很多时候业务方抛给你的问题是一堆场景和约束真正的算法模型要你自己搭。CodeM初赛B轮在这一点上开了一个好头。2.3 参赛策略先保分再攻坚我当时的策略是开场先花五分钟把五道题全部读完在心里按难度排个序然后从最简单的开始做。这里有个经验看通过率比看题面长度能更快判断难度不过刚开始通过率还没稳住所以还是要快速浏览题面。好在B轮前两题确实比较友善我大概是开场20分钟左右搞定了前两题第三题花了点时间想状态设计第四题做了个常规的贪心优化第五题断断续续写了一个多小时最终还是只过了部分测试点。这场比赛最后我的排名大概在前几百名顺利拿到了复赛资格。虽然没有冲进最顶尖的圈层但整个参赛过程让我对“企业算法题”的出题思路、评测机制和难度节奏有了系统的认识。后面再打其他公司的线上赛心里就淡定很多。所以这篇文章我打算把那天的题目一道一道拆开讲讲清楚每道题背后的思路、实现细节、踩过的坑以及复现题解时需要注意的地方。3. 核心题目解析与实现细节3.1 签到题订单编号去重先讲第一题。题面大意是给一批订单编号字符串需要统计有多少个不同的订单编号。输入大小我记得是N不超过10万字符串总长度不超过100万左右很标准的签到难度。解法的思路无非两种扔进哈希表去重或者排序后相邻比较去重。用C的话直接上unordered_setstring然后输出size即可用Java的话就是HashSetString。不过这道题也不是完全无坑。第一个坑是字符串总长度可能比较大如果你用一个setstring底层红黑树代替unordered_set在10万级别的数据量下性能不会差太多但在100万总字符的场景里红黑树的常数会比哈希表高不少极端情况下可能会被卡。第二个坑是如果使用哈希表自定义哈希函数时要注意不要用默认的std::hashstring在部分旧版本编译环境下效率一般。第三个坑是输入输出要用快读快写不能用cin不带同步关闭去读10万行字符串。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; unordered_setstring s; s.reserve(n * 2); // 预留空间减少rehash string str; for (int i 0; i n; i) { cin str; s.insert(str); } cout s.size() \n; return 0; }这道题对应到美团真实业务就是商家后台里统计今日订单量、去重用户ID这种最基础的数据处理任务。虽然简单但它是后面所有题目的起点——你要是连这题都卡住这场比赛的节奏基本就崩了。我的感受是签到题的存在不是为了拉开差距而是为了让选手进入状态同时也是筛选掉那些连基本功都不扎实的参赛者。3.2 二分答案骑手配送调度第二题开始有点意思了。题目大意是有若干个骑手每个骑手负责一片区域的配送给定每个骑手手里的订单数和每个订单的预计送达时间问在所有骑手并行配送的情况下最晚送达时间的最小值是多少。本质上是一个“最大值最小”的问题遇到这种问题第一反应就应该是二分答案。我当时是这么建模的假设我们猜测一个时间T判断能不能让所有订单都在T时间内送完。因为每个骑手同时只能送一单所以给定T之后可以算出每个骑手最多能送掉多少单把所有骑手能送的订单加起来看是否能覆盖总订单数。这里要注意“骑手”之间的订单是独立的不存在单子可以跨骑手分配的情况所以这个判断逻辑是正确的。二分下界取所有订单里预计送达时间的最大值上界取一个足够大的数比如所有时间之和。#include bits/stdc.h using namespace std; int n, k; vectorlong long a; // 每个骑手的订单送达时间 bool check(long long T) { long long cnt 0; for (int i 0; i k; i) { cnt T / a[i]; if (cnt n) return true; } return cnt n; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n k; a.resize(k); for (int i 0; i k; i) cin a[i]; long long l 1, r 1e18, ans r; while (l r) { long long mid (l r) 1; if (check(mid)) { ans mid; r mid - 1; } else { l mid 1; } } cout ans \n; return 0; }这里有个很容易踩的坑二分上界如果取得不够大会WA取得太大又可能在T / a[i]累加时溢出。我比赛时用的上界是1e18结果在C里long long的最大值是约9.2e18所以1e18是安全的。但如果用int去存这个上界直接溢出成负数二分直接死循环。另一个坑是判断函数里的累加可能爆long long所以一旦cnt n就立即返回true避免继续累加——这个习惯在多次二分里救过我。这道题说白了就是经典的“二分答案 贪心判定”对应到美团外卖的场景就是调度系统里预估骑手运力、设置预计送达时间区间的核心算法雏形。后来我了解到美团的配送调度系统里确实有大量这类模型把时间约束、骑手路径、订单优先级揉在一起做优化远远比我比赛里做的这道题目复杂但思想是相通的。3.3 状态压缩红包口令重排第三题是B轮里让我卡了最久的一道题。题面看是一个字符串重排问题给一个字符串s问能否通过重新排列它的字符使得变换后的字符串里不包含任何给定的“禁用子串”。禁用子串数量不多每个子串长度也很短。初看觉得是个字符串匹配题想着用KMP或者AC自动机但仔细一想重排字符串这个操作意味着字符的顺序完全可控所以本质上不是匹配问题而是“组合可行性”问题。我当时想了很久最终用状态压缩DP解出来的。思路是设dp[mask]表示已经选取的字符集合是mask时当前构造的字符串的“某种状态”是否可达。因为禁用子串很短所以只需要记录当前字符串的“后缀匹配状态”即可——就是当前已构造字符串的末尾若干个字符能和哪些禁用子串的前缀匹配到哪里。这样DP的状态就是mask * 匹配进度转移时枚举下一个字符如果转移后不会产生完整的禁用子串就继续。这里最关键的优化是字符集的大小是26但字符串长度N最多也就20左右否则状态数会爆炸。我后来看了题解发现官方的做法也是状压DP但加了一个“预计算所有后缀状态的合法性”的预处理大幅减少DP转移时的判断成本。我比赛时没做这个优化纯暴力在每次转移时都重新做匹配导致最后一组测试数据超时只能拿部分分。#include bits/stdc.h using namespace std; const int MAXN 20; int n, m; string s; vectorstring ban; bool ok(const string cur) { for (auto b : ban) { if (cur.size() b.size() cur.substr(cur.size() - b.size()) b) return false; } return true; } unordered_mapint, bool memo; bool dfs(int mask, string cur) { if (mask (1 n) - 1) return true; if (memo.count(mask)) return memo[mask]; for (int i 0; i n; i) { if (mask (1 i)) continue; if (cur.size() 4) { string nxt cur s[i]; if (ok(nxt) dfs(mask | (1 i), nxt)) return memo[mask] true; } else { // 只保留后4位字符做状态即可 string nxt (cur s[i]).substr(max(0, (int)cur.size() - 3)); if (ok(nxt) dfs(mask | (1 i), nxt)) return memo[mask] true; } } return memo[mask] false; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin s; cin m; ban.resize(m); for (int i 0; i m; i) cin ban[i]; n s.size(); cout (dfs(0, ) ? Yes : No) \n; return 0; }这道题给我的启示是看到“重排 约束”的题目不要第一时间想到复杂的字符串算法先考虑数据范围。N20这个范围其实就是明示“可以用状压”的信号。字符串匹配算法在这个场景下反而英雄无用武之地——因为字符顺序是你自己控制的KMP只能做被动匹配不能指导你主动选择下一个字符。这个思维转变是解这道题的关键也是我文章里特别想强调的一点。3.4 状压DP优惠券最大优惠第4题和第3题都是状态压缩的方向但第4题在思维量和实现难度上都上了一个台阶。题目大意是给定一系列商品和一系列优惠券每张优惠券对应一个商品集合和一个优惠金额某个商品一旦使用了某张优惠券就不能和其他优惠券叠加求在总花费不超过预算的情况下最多能省多少钱。这道题看似是个背包问题但实际上因为有“商品-优惠券”的组合限制不能简单用一维DP做。正确的状态设计是对商品集合做状压dp[mask]表示已经购买了mask集合中的商品时最多能省多少钱。转移时枚举下一张使用的优惠券再枚举该优惠券覆盖的商品子集如果这些商品还没被购买就可以尝试转移。但直接枚举子集的复杂度是O(3^n)级别N如果到20的话根本跑不动。我在比赛现场做的时候N大概是15左右O(3^15)约等于1400万次状态转移勉强能过。但如果N到20的话就必须用“枚举优惠券 枚举其覆盖子集的高维前缀和优化”把复杂度降到O(2^n * m)级别。我比赛时只写出了基础版通过了一部分测试点赛后看官方题解才搞明白优化版的做法。这题算是我B轮里最大的遗憾——明明再想半小时就能写出来的优化当时因为时间压力没敢动。这道题映射到美团业务其实就是优惠券最优化叠加计算。用户在结算页看到的各种满减、折扣、红包组合后台就必须实时算出一套最优搭配才能保证用户看到的金额是准确的。这里的约束比比赛题更复杂因为还涉及品类限制、时段限制、新老客标签等维度但核心的“子集枚举 最优组合”思想是一致的。3.5 压轴题配送路径规划第五题初看是个图论题。题目大意大概是给定一个配送区域的地图有无向带权边每个节点有订单需要配送骑手从配送站出发需要在规定时间内送完所有订单并返回配送站求最短总路程。这个题面一出来脑子里第一反应是“旅行商问题TSP”但仔细看数据范围又没到可以暴力状压TSP的程度节点数量在50个左右边数大约100条里面似乎有很多可以发现的特殊性质。我当时尝试了两种做法。第一种是把问题转化成“最短路 状压DP”——先跑一遍Floyd算出所有节点两两之间的最短距离再用状压DP枚举访问订单节点的顺序。这样做在节点数20以内时可以过但节点数50就爆了。第二种是尝试用DP 剪枝去搜但搜索空间依然很大。最后我意识到这道题可能是一个“伪TSP”——因为在配送场景里骑手不一定需要访问所有节点只需要在时间窗口内尽量多完成订单或者订单本身是可以顺路一起送的所以可能有更简单的策略比如对订单按截止时间排序然后贪心选路径。不过这个思路我没来得及在比赛里验证赛后看了讨论区发现这题确实是一个“最短路径 动态规划”的结合题但核心优化在于预处理“每个订单之间的最短距离”之后利用“订单数量不超过15个”这个隐含条件做状压DP。我当时没注意到订单数量这个关键约束白白在TSP上纠结了很久。这是一个很重要的教训数据范围里的每一个数字都可能是出题人留给你的线索漏看任何一个都可能导致方向性错误。4. 实战过程中的坑与排查实录4.1 TLE从O(n^2)到O(n log n)B轮里我遇到的最经典问题是第三题的TLE。原因是字符串重排那道题我用每次转移时都重新做子串匹配的方式导致同样是状压DP别人的复杂度是O(2^n * n * 子串长度)我的复杂度是O(2^n * n * 构建字符串长度 * 子串长度)多了一个倍率。在限制时间2秒的情况下这个差距被放大了。排查的过程是这样的我先在本地用随机数据生成器构造了一组N20的极端数据跑了一下耗时是4.8秒明显超出限制。我加了一些计时输出chrono::steady_clock定位耗时发现瓶颈在于每次substr和字符串拼接都产生了临时对象而我又在unordered_map里存了整个字符串作为状态key导致状态转移时哈希计算的成本也高。后来改成只存“最后4位字符”作为状态key后时间降到了1.7秒左右本地通过了。但比赛时因为提交次数限制我没有把优化版在线上验证这是一个失误。从这里我学到一个通用技巧状压DP里如果状态里要带字符串信息千万不要存整个字符串而是应该想办法把字符串压缩成整型或短字符串。这既降低了哈希成本也让状态空间变小代码反而更容易调。4.2 位运算优先级带来的WA第二题二分答案的代码我一次就写对了但第四题状压DP里我栽在了一个很隐蔽的坑上位运算优先级。C里!、~、、、、^、|的优先级各不相同其中按位与的优先级低于相等判断高于按位异或^。所以如果你写if (mask (1 i) 0)实际执行的是mask (1 (i 0))完全不是你想的那个意思。我当时写的是if (mask (1 i) 0) { // 打算判断第 i 位是否为 0 }这个表达式在C里的实际解析是mask (1 (i 0))只有当i 0时比较的是mask 1其他时候简直是灾难。比赛编译器不会报错逻辑完全错误debug时肉眼很难看出来。正确写法是加括号if ((mask (1 i)) 0) { // 才是判断第 i 位是否为 0 }这个问题在阿里、腾讯、美团的笔试里都出现过类似的变身我后来带新人时也经常提醒位运算表达式一律加括号不要省。这不是风格问题是正确性问题。4.3 评测环境与本地不一致还有一个比较玄学的问题是比赛时我本地用C11编译通过并运行正确的代码提交后却出现了编译错误。后来发现评测机用的是C14默认开了-Wall -Werror很多warning会被当成error处理。比如我用了一个未初始化的变量本地编译器只给warning评测机直接编译失败。从那以后我养成了一个习惯写算法题代码时把所有变量都初始化所有可能出现的隐式类型转换都显式写上所有没用到的变量直接删掉。不要觉得这是小题大做在线评测系统为了保证判题公平编译参数往往比本地严格得多。这个习惯后来在去美团面试时也帮了我——面试官让我手写代码的时候他看我代码里变量都有初始化还特意夸了一句“代码习惯好”。另一个评测环境相关的坑是内存限制。B轮的题我记得内存限制是256MB这会导致一些很自然的写法MLE。比如第三题如果用unordered_mapstring, bool存状态每条字符串key本身占几十字节N20时全量状态可能达到数十万到上百万内存很容易超标。我比赛时没遇到这个问题但赛后看了别人讨论确实有人因为MLE挂在这题上。我们平时做算法题时通常只关注时间复杂度和空间复杂度的“大O”但在实际评测系统里常数因子、语言特性、编译参数都会成为压倒骆驼的最后一根稻草。4.4 常见问题速查表现象可能原因解决办法TLE状态转移时重复计算过多预计算所有状态转移的合法性减少重复匹配TLE使用了set而非unordered_set改用哈希容器并预留容量避免rehashWA位运算表达式优先级错误为所有位运算加括号不要依赖默认优先级WA二分上界太小或整数溢出用1e18配合long long判定函数内提前返回MLE状态key用完整字符串压缩状态只保留必要的少量字符或整型编译错误未初始化变量被-Werror拦截所有变量显式初始化杜绝warning5. 赛后复盘题目难度梯度与个人排名比赛结束后我花了大约一个下午把所有题目重新做了一遍重点研究了我没完全AC的第三题和第五题。复现题解的过程其实比比赛本身更有价值——因为比赛时处于高压状态思路很容易被带着走而赛后复盘可以慢慢思考把每个细节都吃透。复现第三题时我按照官方题解的做法预计算了一个valid_transition数组事先枚举所有可能的“后缀状态 新字符”组合判断转移后是否合法。这样在DP主循环里每次转移只需要O(1)的查表时间整个DP的复杂度降到了O(2^n * n)在N20时勉强能跑。复现第四题时我用了一个二维DPdp[mask][j]表示已经购买了mask集合中的商品且最后一张使用的优惠券是j时能获得的最大优惠金额。转移时枚举下一个使用的优惠券以及它覆盖的未购买商品子集用高维前缀和优化掉重复计算。这一步优化落地后代码跑出来的结果比我比赛时写的版本快了三倍以上。复现的过程让我确认了一件事B轮前三题其实都是“可以拿满分”的题只要时间分配得当。第四题是一道需要一点灵感和临场优化能力的题拿到部分分是正常现象。第五题则是用来区分顶尖选手的普通参赛者在这里做好“尽力拿部分分”的心理建设就好。这个难度梯度设计得很合理它让不同层次的选手都能有收获也让真正的高手有机会展现出完全碾压的代码速度和思维深度。我最终的排名大概在晋级线以内的后段从名次上看不算亮眼但这场比赛的收获远超一个名次。因为我在赛后复现题解的过程中把“状态压缩DP”这个知识点的熟练度提升了一个台阶。后来我在面试算法岗的时候遇到了一道美团面试官出的、和第四题非常相似的优惠券组合题我直接把比赛里学到的优化方法背了出来面试官当时有些惊讶问我是不是做过原题我笑着说是的我在CodeM B轮里踩过这个坑。6. 这类比赛对日常开发的反哺很多人觉得参加编程大赛是学生时代的事情工作了以后就没必要再刷题了。但作为一个在互联网公司写过几年业务代码的人我想说这个想法是有问题的。算法竞赛锻炼的“抽象问题能力”和“边界条件敏感性”在平时开发里几乎每天都在用。CodeM B轮那些题目表面上是在考算法实际上是在模拟工程师从模糊需求里提炼数学模型的能力。举个例子第三题的“重排字符串避开禁用子串”看起来和业务开发八竿子打不着但它的核心是“在约束条件下搜索可行解”——这和我在配置中心里做“灰度发布策略校验”时的思维方式几乎一模一样。第四题的“优惠券组合最优解”就更直接了营销系统里天天要算满减组合虽然业务规则更复杂但基础算法模型就是比赛里的那个状压DP。我甚至后来在代码评审里看到有同事写过一版“优惠券最优组合”的实现用的就是朴素枚举加剪枝我当时指出来可以用状压DP 前缀和优化那个同事看完之后恍然大悟。在CodeM这样的比赛里你可能学到的不是某个具体的API怎么用而是“如何把大问题拆成小问题、如何设计状态和状态转移、如何定位复杂度的瓶颈”。这些东西很难通过看文档学到只能通过一遍遍调优代码、分析超时原因、研究别人题解慢慢积累。所以我一直建议身边做开发的同事哪怕不追求拿奖每年也去参加一两场编程比赛。不需要专门花很多时间准备就当是给大脑做一次维护性体检顺便看看同行的水平线在哪里。7. 最后说点个人体会CodeM 2017初赛B轮已经过去很多年了很多细节我可能记得不精准但那场比赛对我产生的影响一直延续到现在。它让我认识到算法题不只是刷题工具它背后往往藏着一个公司对工程师能力的真实期待。美团愿意花这么多精力办CodeM这样的比赛本质上也是希望通过这种方式发现有潜力的人才。如果你正准备参加类似的企业编程比赛我有几条实在的建议。第一赛前至少花两小时熟悉评测系统的操作别在提交按钮在哪里这个问题上浪费比赛时间。第二比赛时先扫题、再排序、后动手把“拿分”放在“秀操作”前面。第三赛后一定复现所有题目尤其是那些你只拿了一半分的题复现一遍顶得上新刷十道题。第四注意代码的编译可移植性变量初始化、位运算括号、快读快写这些细节关键时刻都能救命。第五不要因为一场比赛的失利而否定自己CodeM B轮我第五题几乎没做出来但前面几题拿到的分依然足够晋级。比赛是综合能力的比拼不是单题的输赢。我后来还会时不时翻出B轮的题目重新做一做每次做都会有一些新的感悟。算法水平不是线性增长的它更像是一层一层垒上去的你可能在某段时间觉得停滞不前但只要持续积累到了某个节点之前的困惑会一下子连成线。CodeM 2017初赛B轮就是我算法路上的一个节点现在把它写下来希望能给后来参加这类比赛的你一点参考。