50th ICPC Regional 沈阳站游记

· · 生活·游记

:::align{center}

Prologue

:::

本来准备去的是武汉站，然后为啥没去成呢？因为教练忘记交报名表了。

我们直到报名截止后 3 天才从在武大上学的 kb 那里得知忘记填报名表的事，立即就紧急排查之后还有哪一场 ICPC Regional 可以参加，然后发现沈阳是最合适的，再往后太靠近 NOIP，再往前已经无法报名了。

申请名额，然而我们学校只申请到了一个队伍。原本计划的三个队伍只留下了我，@StayAlone 和 @LPhang 的队伍。由新教练带领我们去沈阳，至于新教练她自己，她甚至申请到了一个正式队伍和我们一起打。

在 PTA 上摸爬滚打了半天终于报上了名，在起跑线上打败了洛谷科技。 然而最后打星队还是通过 Excel 报名的。

总之，ICPC Regional，Launch！

省流：

念到我请华丽地往上滚 队：

:::align{center}

Day -1

:::

在凌晨严肃到达沈阳。其实这个时候还没有冷锋过境，晚上依旧有大约 6^{\circ}\text{C}，所以我穿着少薄的羽绒服也没有感觉很冷。

到达酒店之后我感到很无聊，还很困，最后几乎是立即就睡觉了。SA 和 ph 一直玩到三点钟才睡。

第二天我醒的最早，但是由于他们没有醒我只能一直醒一直睡/yun，最后大概在 11:30 左右三个人都醒了。然后就排查中午吃什么，最后选了一家就近的东北菜，我们出门的时候还不知道有多近，结果就在酒店的左手边。

我们点了一个 2 到 3 人餐，本来以为我们肯定不够吃，直到服务员端上来盘子里面像山一样的白菜拌蜇皮。

接下来就是较为痛苦的吃不完硬撑环节。最终我们消灭了大部分的荤菜，零部分的素菜。 除了我一个人把白菜拌蛰皮那座山吃秃了，因为上凉菜的时候我还不知道会发生什么。

:::align{center}

Fig1. 几乎是清扫干净的战场。中间是东北的回锅肉，它后面的京酱肉丝很好吃。右边是被我吃秃顶的白菜拌蛰皮，它后面也是一道非常好吃的炒猪肝。左边的烤鸭被我们吃干净了。饭几乎没动，但还是花了 9 块钱。 :::

吃完饭本来准备四处走走，但 ph 说现在不想动可以晚上再说，所以最后还是选择了回酒店。因为热身赛要晚上 6 点才开始，下午在酒店呆着依旧很无聊，所以我和 SA 睡午觉，ph 继续玩崩铁。

一觉睡醒怎么天黑了！但是我打开手机一看才 5 点。才发现原来这里四点半就日落了，感觉很奇妙。

再磨蹭了一下就出门了。一开始以为教练找了一个没那么远的酒店，打车才发现这个酒店到东北大学有 20 分钟车程……和我上学差不多远了。紧赶慢赶还是赶在热身赛开始之前签了到，找到了我们的座位。

坐下之后就听到裁判组说有 communication。再然后就发题了。看了一下 A 是 communication，B 是 ECF 试机里面那个简单交互题，C 不知道是啥，D 是圆形面积并。

我先上去写 B，过了之后开始思考 A。一开始没看到 run-twice 传回来的可能是 \operatorname{reverse}(S) 以为是简单题，结果发现另有玄机。然后我就开始爆完全没有任何道理的假算法并往上交，最后 SA 拯救了我 shitting 的大脑，敏锐地指出偶数的时候那 1 bit 用来传第一个不相同的位置在左还是在右，然后我们成功在 4 tries 通过了这个题。

我 shitting 假做法的间隙 ph 快速通过了 C。由于我们完全不会圆形并板子（此时我们还没有打印任何板子），所以过完 A 之后我们就走了，只花了 37 分钟。

吐槽一下东北大学发的这个气球特别不牢固，非常容易和杆子身首分离，所以我们最后拍照的时候非常艰辛地才把插气球的板子拿起来，因为只要一拿起来气球就会飞走。

我们在东大的外面找了一家兰州拉面作为晚餐，然后选择遗弃很容易到处飞的气球骑共享单车回酒店。

:::align{center}

Fig2. 路上经过了南湖公园。 :::

回到酒店的时候鼻涕都给我冻干净了（我处于感冒状态）。点了奶茶喝之后就开始找打印板子的地方，然后发现这里的打印店晚上 9 点就关门了，折腾了一会我想到酒店肯定可以打印，于是最后在前台打印了我们 56 页的板子，甚至只收费了 9 块钱……

顺便解决了早餐券的问题。教练送来了非常难吃的感冒药，我和着水艰难地吃掉了。

晚上 12 点所有人准时地睡觉。然而睡不着，我选择听 ASMR，然而 SA 嚷嚷着要聊天，我在他们俩聊天的声音中睡着了，剩下的就不知道了。

:::align{center}

Day 1

:::

早上我第一个醒。感觉有点肚子不舒服。难道又是经典比赛日拉肚子吗？

上了个厕所就好多了。上完厕所 SA 和 ph 也醒了，告诉他们时间不早了就抓紧收拾了一下行装，到酒店的餐厅开始吃早饭。

吃完早饭舒服多了。下楼的时候已经八点半了，幸好一路上都不堵车，时间还来得及。

最终在 8:55 抵达了赛场。面到了 @shinzanmono，我指出我们在 THUSC2024 的时候已经换过徽章了，但他还是又给了我一个。我已经把包放到后面了，所以准备考完再给他我的。

由于本场比赛要上 Universal Cup，接下来的部分涉嫌剧透。不想阅读剧透内容请向后滑到下一段加粗文字。

分配了一下题目。ph 阅读中文题面，我和 SA 读英文。因此 SA 开 ABCD，我开 EFGH，ph 开 IJKLM。

开考。我发现 E 里面有神秘希腊字母于是跳了（最后发现是 \pi 表示排列……），F 看起来像博弈论也跳了，G 里面有双重积分号直接跳了，H 看上去比较像正常的题，并且是我和 ph 较为擅长的数数，于是先读 H。然而读了半天读不懂。

阅读中文题面的 ph 很快指出 I 是签到，于是先让 ph 写 I，写完一发过了。

然后 ph 指出 M 也是签到，于是又让他上去写 M，写的中途 SA 和我讨论了一下 B，我很快会了，于是等待 ph 写完 M 我去写 B。

等待 ph 写 M 的过程中我阅读了一下 A 和 SA 的初步转化，看着像个离谱题，暂时没什么思路。SA 说 C 是 communication，D 是离谱 n\le 9 题，于是我们认定这两题不可做。

看了一眼榜，发现 K 有挺多人过了，于是我开始看 K，这题也太离谱了吧？！

ph 写完 M 一发过了，我上去写 B。先交了一发贪心 Wrong Answer。我自嘲自己写什么都会变成战犯。

发现自己在 shitting，改了一发依旧 Wrong Answer。

没招了。改成最暴力的前缀和写法，枚举插入多少个有色图层，终于过了。

写完 B 下来 ph 跟我讲了 J 的转化，就是求区间在值域上的最大间隔，一看就是数据结构题。于是把这个题扔给了 SA。我指出这个题是莫队，可以维护区间的最大间隔和次大间隔，然后把查询的 v 插进去即可。然而直接莫队要带 \log，SA 指出经典 trick 改成不增加莫队然后用链表掉 \log 应该是奏效的（我们深信不疑可以在仅合并的情况下维护最大值和次大值，然而这显然是错的，如果我们合并到了次大值和它的旁边那么次大值就丢失了）。这显然很难写，于是我们决定在没有题写的时候 SA 去写这个巨大难写做法。

看了一眼榜，此时 K 过了一车人，但是我完全没有思路。于是丢给了 ph，我来想另外一个过了很多人的题——A。

刚让 SA 坐上去写他就一脚踢松了显示器电源线（伏笔），于是我们花了 5 分钟让志愿者找工作人员来给我们接线。

这个 A 显然要二分，但是 check 复杂度太高了。让 d=i-j 化了一下式子，我发现只需要 check \sqrt{\frac{mid}{a}} 项，但是答案上界有 4\times 10^{18} 的样子，还是太高了。

同时 ph 发力了一下就会 K 了，他说是诈骗题，于是让 SA 让开写了一下，一发过了。

在 ph 写 K 的时候我说我猜还是不用 check 这么多项，并尝试能不能把上界证严一点，但我失败了。我说一会有机位了给我验证一下结论吧。

ph 过 K 之后我就上去写，我把 d 的上界开到 10^7，然后 TLE 了。我猜 check 里面这个 j 的界相对 d 是单调的，于是加了一个剪枝，然后就跑出来了！

和 ph 理性讨论了一下要不要交，然后被 ph 的 n=10^6,m=10^{12} 数据叉了。虚空调试 10 分钟之后发现 {n\choose 2}<m……把 ph 骂了一顿之后我删掉了调试开始重测样例。

然后我就莫名其妙按到了神秘快捷键把电脑锁了。于是我们又花了 5 分钟找工作人员给我们开电脑，最终发现开电脑方式是在 username 一栏输入 team。

打开电脑我又测了一遍样例，确认无误并且极限数据能在 4 秒之内跑出来之后就交了。

CORRECT！

这猜的上界猜的单调性真是对的啊？？？

于是我下来换 SA 继续写 J。看了一眼榜发现 F 和 G 过了很多，但 G 是那个双重积分计算几何，读了一遍 G 我认定这个题貌似对高中生不可做。考虑到半个小时之前西交的队伍因为抢到了 C 的首 A 欢呼雀跃，而 ph 此时似乎已经会了 F，所以我们开始看 C。

然后发现 C 是个纯种思维题，我的思维水平根本想不进去这个题，连一点思路都没有。然后我发现 ph 的 F 假了，简单修了一下貌似又对了。

然后我和 ph 继续看 C，然而还是一点头绪都没有。此时 SA 传来捷报，J 已经过样例了（大约 205min）。但是为了保险我上去写了个对拍，并造了一组大样例，然而拍一组挂一组。

我决定停止看 C，尝试做 G。画了一下我发现 D 实际上是闵可夫斯基和状物，把积分理解成面积和一堆一堆小方格非常方便，然而就在我画图在样例上验证结论的时候 SA 声称 J 假了，此时已经 220min，我被迫放掉 G 去帮他们忙。

我和 ph 让 SA 尝试写一下简单的 \mathcal O(n\sqrt n\log n)，然而这玩意 T 飞了，本地测试受 multiset 逆天常数所赐需要跑 140 秒。于是 240min 时我紧急被征用上去写 F。

然后发现 F 细节越写越多。一直到 270min 的时候我已经精疲力尽不想写任何代码了。ph 声称他会写 F 了，SA 也声称他修出来了，只需要保留原来的回滚莫队和链表，合并改成用分块来均摊地根号平衡即可，不要再维护最大值和次大值了。SA 对自己能否在 30min 内写完表示怀疑，考虑到还有可能被卡常，于是我们最终决定让 ph 写 F。

然而最终 ph 也没有调通，反倒是三个人都红温了，我们都有在手上没过的题。

观察了一下周围。得知教练单挑没有过 K，但是通过对拍的方式过了 F，流泪了。学长 yhy 的队封榜前喜提七题，接近校排杯线，太牛了。ph 说在柚子超玩会看到了草八牛，怎么这么牛。

非凸在一片混乱中开始了企业宣讲，然后是讲题，发现我们的 FGJ 做法都正确 /ng。又等了一会就滚榜了。滚榜挺无聊的，不知道为什么滚榜主持人看上去非常没有工作欲望。

主持人把我们的队名念成了“念到我清华丽地往上滚”/oh。然而我们并没有华丽地往上滚，反倒是 155 分钟之后一直在坐牢。不过好在最后凭借五题罚时 443 稳上了金线（rk31），拜谢猜结论，这招完全属于是机制怪。

:::align{center}

Fig3. 最终的五个气球。桌子上的纸是共 12 页三个版本的 J.cpp，还有 F 的题面以及上面画的一堆 DFS 树。 :::

最终非常感慨我这次居然为队伍做了一点正贡献，我难得在 XCPC 里面帮队伍过了一个题。然而很遗憾的是 CQYZ 计算几何皇帝最终没有过（可做的）计算几何，被积分号严肃吓倒了。另一个教训是再也不给 ph 做图论题了（赛前 vp ICPC 2024 Shanghai R，ph 执意不建圆方树，成功在十余发提交之后解决了银牌题）。

szm 溜得太快了，我和 SA 忘记了给他徽章 /ng。最后决定 WC 再给他。

从这里开始不再有剧透内容。

于是我 OI 生涯中的 XCPC 的打星之旅似乎就到此告一段落了。其实如果运气好 NOIP 没退役还能打上一次 ECF，但我害怕到时候身边的人数不再完整了。或许连一个完整的队伍都凑不齐呢？……

果不其然地迎来了戒断反应。我一直觉得我热爱的事情是算法竞赛而不是竞争，所以打星参加 XCPC 对于我来说仿佛变成了一种解药，它脱离了 OI 的压力和焦虑，我在这五个小时里感受到的是纯粹的解决问题和观察性质的美好。

也许等到我正式参加 XCPC 时，我又会推翻上面的话，把 XCPC 打成 OI 一般的充斥着压力和焦虑的东西吧。哎干嘛要想那么多。总之算法竞赛仿佛已经变成我不能失去的东西了，这应该是真的。

感觉很难想像彻底离开算法竞赛界的一天，又或者其实根本不会有那一天吧。
——@cool_milo《CCPC2025 济南站被翻盘记》

上大学之后又会以怎样的样子继续我的算法竞赛之旅呢？说来我的 OI 生涯快结束了，但算法竞赛才刚打到一半，我还有十多道题没有出出去，仿佛一切还和 5 年前这时候我穿着羽绒服坐在 CQYZ 的机房里一样，什么都是新的，什么都是未知的，什么都会好起来的。