SYSCPC Final 2024 参赛总结

赛前

前一天下午回家过冬至，出去外面吃粤菜，在一家环境很俗的小店，但是人奇多，应该是老字号了，但烧鹅挺赞的。冬至并没有吃汤圆。

早上六点起来，从家里到纪中，然后七点钟坐小巴到中大，大概在八点多到达。

到场地，是分很多个机房比赛，发现送了保温杯，其实还送了衣服但直到结束我们都没有发现。

我和 zy 与 lyz 一队，纪中一共有十一个队。这是我第一次在现场打 CPC 类型比赛，题面是全英文的。

我们带了一点点巧克力，然后只带了一本没有什么用的算法书，还有词典与一张“ACM 常用词汇表”。注意我们并没有带任何代码，这为后来埋下伏笔。

我们听说还会发午餐。ZnPdCo：可能是盒饭韭菜盒子？

系统是 ubuntu，VS code 已经配好了，感觉很流畅。

赛时

这是赛后得到的题面：https://codeforces.com/gym/105631。

比赛九点钟开始，比赛一开始，我们队先看了 A 和 M，发现 A 是签到，在 5 分钟时过了。而 M 是构造，我们想了一段时间觉得并没有突破口就不再想了。

过完 A 后，很快就得到了第一个气球。然后我们队开始看 G 和 K，zy 说她会了 G 写了一个分块，然后陆续 WA，最后成功 TLE 了，原来是她的复杂度算错了。

不过没关系 lyz 又对 K 有思路，他写完后发现样例过不了，我重新思考，改进了一下他的思路。就是枚举极差，然后计算极差的方案数，对于每个长度求出选 \(m\) 个且极差为该长度的方案数，用总数减去不合法的方案数，发现可以递推，对于长度 \(i\)，

就是对前缀和求和。时间复杂度 \(O(n\log m)\)， 因为有快速幂。

我们看榜，决定先做大众题。接下来 zy 看 D，lyz 看 J，他们分别想到了做法，其中 D 题大概是树形 DP。而我则看 L。

他们也顺利地分别过了 D 和 J，我们似乎得到了非正式选手中的前 6 名？

而对于 L 题，在 zy 与我的合作中，我们提出了一个看起来很对的做法，就是先把所有位置填上 \(\text{lcm}\) 或是 \(\gcd\) 然后再把对角线换掉，在我实现完后，很不幸它 WA 掉了。随便举了一个例子，发现要特判 \(n=1\) 或 \(m=1\) 的情况。之后很高兴它 AC 了。

过了 6 道题后，我们已经成为了显示上的 rk1。

接着我才发现 C 题是模拟，直接做，我赛时并没有想到排 26 次序就好了，而是想着时时刻刻动态维护，想着要查排名，就用 pbds::tree 吧，结果发现我忘记了查排名的函数，赛后发现原来是 order_by_key，而查 k-th 是 find_by_order，这就体现出还是要带上一些代码资料进场的。同时我们的 VS code 也没有补全函数，这个方案最终失败了，此时大概是十一点半。
这时 lyz 提醒我能不能树状数组呢，发现是可以的，只要离散化就好了，终于在十二点过了 C 题。
赛后还是发现太蠢了，没有考虑到只有 26 次的排序做法。

此时我们过了 7 道题，然而变成了 rk3，因为 C 切得太慢了。

十二点了，感到有点饿，但还是没有发午餐，看榜时惊奇的发现 wtc 与 crazy_sea 的纪中一队已经 AK 了，且没有罚时，毫无疑问他们将成为第一名。

我们决定看 F 和 G。zy 与 lyz 看 F，我看 G。然而二战转折点来了。

他们大概在十二点半开始写 F，我也对 G 有了一点拆位的想法。

然而他们不断 WA，终于在一点多时 TLE 了，时间已经不多了，我的 G 题感觉并不对，于是决定去救 F 题，如果过了就翻了。

一点钟终于发了午餐，是麦当劳，有可乐、包、麦乐鸡块，每人都有这样一份。

等我去救 F 时，发现代码有很多边界问题。他们写了一个 \(O(m26^2\log)\) 的做法，经过我的一番指导，他们能够把 $\log $ 去掉。

然后呢？就没有然后了，此时已经封榜了。我们还是不断的 TLE，他们觉得是常数问题？我们尝试把 map 换成 unordered_map，把 string 换成哈希，然而还是一直 TLE。即使 zy 能够把 $\log $ 去掉变成 \(O(m26^2)\) 还是无济于事。此时已经一点半了，再做不出来就输了。
我开始感觉像是内存越界等问题，而不是常数（这三个人还不知道原来正解就是 \(O(m26^2)\)），因为理论上这个复杂度是能过的。
但是在之后的时间里我们还在优化常数，或许让我再重构一遍代码就能过了。我们也就一直耗到了比赛结束。
最后半小时，发现确实有数组越界，他们写了 string，结果调用下标却超出范围，我有些生气。

总之，我们再最后两个小时，没有得到一分。

到最后的一段时间，我几乎是在享受午餐了，板烧鸡腿堡和甜酸酱配鸡块挺赞的。

总结

Summary：

• 这次的比赛策略有些不太对，我们主要根据排行榜确定开题顺序，导致我们到最后有一些题都没看，应该通读所有题的。这导致了我们在切题速度上不太正常。而且最后我们几乎是在死钻一两题。
• 在这场比赛中，我显著地感受到我的两个队友的代码、调试能力和运用 STL 等的能力并没有我强，或许可以只让一位代码能力强的人写代码，其他人提供思路，这样在代码风格上也比较统一，方便题目的切换与调试。
• 到比赛的最后，我仍不知道 F 题的做法，然而我的队友的做法已经是对的了，如果让我来这道题的代码，我们最后的结果可能会好一些。总之就是一定要与队友分享题目的做法，这样大家可以一起思考与调试代码。而独立想、独立实现的模式在前面几道简单题可能会比较适用，而一到后面关键性的题目时，就出现大问题了，这也解释了为什么我们队的后劲不足。
• 总之，这次比赛是一次独特的体验，与平时自己思考、自己做题的模式不同，由于三人一组，它更考验团队之间的默契与配合度，这可能需要在赛前与队友好好磨合才能得到令人满意的程度，包括熟悉队友的代码风格与思维模式、制定合适的分工与比赛策略而不是自顾自的。

赛后

我们去听了中大的一个基金会的成立仪式，总之跟我们没有什么关系就是了。

纪中的梁校也受邀参加了活动并做了发言。

最后的最后是滚榜环节，十分 interesting，各个队伍还有自己的图，滚榜时会显示出来，奶龙成分过高。以我的理解，实际上每个学校只有三个队被确定为“正式队”，只有这些队在榜上，而颁奖则只有中大校内的队伍有份。最后也是前五名全都是中学队伍，成功实现了中学生暴打大学生，纪中一队也毫无疑问成为了第一。而我们队过了 7 道题，达到了 Ag 的线，纪中其他队都大部分是 8 道题，而 8 道题的低罚时就有 Au 线了。

过程中，我们还看到了古神上台发言，还有纪中在中大的校友与各教练和校长合影。

最后的最后，所有纪中参赛选手、校友共同合影。圆满结束。

坐小巴五点半开始返校，七点到学校，在翠影吃了鸡扒叉烧滑蛋饭。

THE END

2024 就要结束了，提前祝新年快乐，祝我自己 2025 年 RP++！