ICPC EC Final 2022 游记

Day -1

想着早点到上海,留出点时间随机游走,于是订了足够早出发(十点整)的 G7 次的车票。结果就是不得不八点多出门赶车。

运气不太好,没赶上早高峰房山线跨线进 9 号线的车,换乘次数 +1。

到北京南站的时候离开车差不多半个小时,过了安检上楼之后刚好赶上开始检票,冗余时间感觉不太充足。

上车的人是真的多,怪不得京沪高铁能赚钱()

订的票很不幸地是 01 排,结果就是面前没有座位了,对于我们这样的三人连座来说,由于过道在车厢中间位置,桌板的大小缩了不少,坐在靠过道的我为了用上桌板还得往窗户那边凑过去。

虹桥 2 号航站楼的伪虚拟换乘挺有意思。名义上是虚拟换乘车站,但是可以在中间两个轨道停车的时候通过穿过车厢的方式实现换乘。

在同济的高中好友邀我去看花,然而发现四平路离宝山并不算近,再加上身心颇为疲惫,只得婉拒,颇为遗憾。

晚上我校的几个队(可惜 ddl 不在)找了个上海菜馆恰饭。菜馆是对着 知乎上的一个清单 找的,味道确实不错,很符合我对上海菜的想象!

Day 0

一大早三个人一块到学校附近的购物中心觅食。可惜九点多对商场来说还是有点早,转了一圈没找到几家开门的店。本来想吃汤包的,最后结果则是吃了生煎。

签到出场之后意外在体育馆门口遇到了 懵哥。然后发现 江莉 此刻也在体育馆内,于是我们两人一块去找江莉要了一张合影。

在体育馆门口随机游走一波后没遇到啥群友,然后被懵哥拉到了一个学校对面棋牌室线下打起了日麻。

虽然打的是日麻,但是这个棋牌室也不是日麻雀庄,用的麻将和麻将机还是按国内麻将设计的。结果就是麻将牌大了一头(其实也没碰过大洋化学生产的小麻将牌,但就是感觉到大)。虽说没有点棒,不过房间里还有筹码,倒也问题不大。

打了两个半庄的牌,某位群友运气真的离谱,又是无役河底又是二杯口听牌,各种稀罕事情都碰上了。

热身赛主要是熟悉了下命令行提交程序的脚本,比网页端选代码提交方便不少是真的。另外确认了下 VS Code 扩展的实装情况。

热身赛现场面到了 SJTU 的 installb,算下来我们差不多四年前就认识了,然而因为种种原因一直没有面基过();还面到了 XDU 的 Ynoi,树剖可爱捏;以及 SDU 的 扶苏,确实看上去「非常具有青春活力」(SHU 某领导语)。

接着去 WHUT 的「树上猫猫虫」队机位捉 EA,绒绒和 yizr。EA 竟然没把我认出来,明明上次见面仅仅在一个月之前,有点郁闷(x)。然后发现湖北各高校的队似乎都在,于是捉到了 WHU 的 hls 和 Dew。

感觉湖北的算法竞赛圈内部 connection 好紧密啊,无论是 OI 还是 XCPC 都是如此。

之后进行了一波 EI 群群友面基,然而 EI 群面基却没有 EI,怎么会是捏?

晚上听说 RUC 的「复旦栋梁」队名惨遭连夜和谐,非常离谱。

睡觉前队内再次进行了一遍事项确认,毕竟是线下赛,很多事情和线上赛还是没法比的。

  • 每提交一次代码之后都打印一遍代码,然后立刻把机位交给队友;
  • 比赛不同时间段该做的事情,机时的分配策略,以及何时该弃题(说实话这些策略实际执行的情况并不算好…);
  • 确认了明天要带的书。

Day 1

早上还是吃生煎,吃完进体育馆的时间还不到九点,体育场里有些座位还都是空着的。

开幕式没啥太有意思的环节。

十点比赛准时开始。

(由于咕咕咕,下面的回忆情形可能与实际情况存在一定偏差)

简单调了下 IDE 环境之后开始看题,很快发现 M 是签到题,刚准备上机敲代码,旁边 BUPT 队就把这题过了,拿了全场一血,真的快。

签到写得非常顺,其实感觉挺稳的,不过还是按照赛前的策略在提交后马上打印了代码。转头去看大屏幕上的实时队列,过了,果断下机。

队友 indogent 开始写 C 题,这时候正好抽出时间过一遍全部题目。先确认了 F 题是交互题,K 题是只有 16 MB 的特别题。

读完所有题之后发现 L 这个构造很有意思(灾难发挥开始),决定先手玩点小的 case。不久就发现了最优解应该是 \(4 \times 4\) 的周期性 pattern,胡了一个 pattern 后刚好赶上队友交 C 题没过,果断上机开敲,这时候距离比赛开场大概 30 分钟。

这时候虽然不少队伍都交了这题,但还没队伍过,预感到这题应该并不简单。测了样例,再加上几组手玩数据,(看上去/自认为)没问题,先交一发试试看,不出所料寄了。

果断下机在纸上继续手玩。枚举了下 \(n, m\) 对 4 取模余数不同的情况,发现不同情况下最优解的 pattern 是不一样的,应该是由原来的 pattern 根据余数循环移位一定的行得到,加了循环移位后, 1 的数量确实比之前更多了。发现这一(伪)结论的我大喜过望,趁着队友第二次 C 题挂掉,上机改了我的程序,结果还是错。特意确认了 \(n, m < 4\) 的 corner case 没有问题(?)后,找到了一个细节问题,改了改之后依旧没过。

C 题远比想象中要坑不少,虽然输入都是 long long 范围内,答案却有可能超出这个范围,还得用 128 位整数。不过最后还是顺利地过了。

然后 Ceon 写 J 题,意识到 L 题坑多的我决定先把这题放了。又过了一遍所有题,这次盯上了图论题 I 题。先考虑了下两个人都在起点的情况,发现这时候直接走最短路就一定最优;如果两个人起点不相同,则可以以胖触发传送这个时间点把问题分为两个阶段,触发传送后两人处于同一起点,问题变成了前面的情况,把触发传送前阶段的最短路和触发传送后阶段的最短路拼起来就是答案了。

J 题很快过了,我立刻上机敲 I 题。当时交互题 F 过的队不少,过 I 题的队反而不多(最后 I 也就比 F 多过了十几个队)。为了求稳敲得其实没那么快,还特意确认了下完全没有触发传送的 corner case 没有问题。提交之后一发就过了,当时感觉挺惊讶的。

到这里平稳发挥的部分结束了。现在看来,前期虽然做题速度并不算非常快,但真的是一分钟机时都没有浪费。

意识到 F(看起来)是个简单题后,队内开始全力攻 F。indogent 很快根据容斥推了个 \(4n \log n\) 的做法,不愧是做奇怪题的高手。虽说这个做法离 \(2n \log n\) 的正解还有点距离。

由于 F 极高的通过数,大家也都没心思想其他题了。而 F 题却久无进展,这应该是比赛中最难受的局面了。

看着机位空着,大家一块罚坐,我决定再尝试下突破 L,果断上机再测几组数据观察。然而,对着那么多手测的 case,我却完全没有发现有些输出其实并不满足所有 1 连通的要求,也许是因为队友注意力放在别的题身上,我把我的算法和结果讲给队友们看,他们也没意识到这个问题。

封榜后 indogent 和我说 H 其实就是个暴搜(但是不太好写),可惜最后不到一个小时时间,实在是过于紧张。最后我们的成绩就此定格在了 4 题。

这个成绩显然是寄了,甚至一度感觉这次要打铁滚粗了。当然由于前期节奏还不错,罚时其实还是有点优势(最后排名 4 题第四),倒也稍微安下心来。

走出体育馆之后,校内的四个队一块拍了张合影。拍完合影后,其实本来想着是进城逛一圈的,不过因为晚上的洛谷恰饭还是在学校周边的商场,就不好跑太远了。

最后决定去找退群的群友。发现这时候华为正在做技术讲座,现场还有小点心之类的。

EA 他们也来了,不过昨天 EA 没把我认出来,今天我没把 EA 认出来,乐。

捉到了 foreverlasting 的学弟 Owen_codeisking

华为的活动结束后,距离晚上约的恰饭时间还有很久。于是我和 EI,论文鸽等人就在大厅里坐着闲聊起来。看着志愿者们开始收拾场地,把各队的队牌,气球陆续搬走,应该是为明天的华为挑战赛和闭幕式作准备吧。

晚上的洛谷恰饭,主要是题管组的群友,以及在洛谷网校讲过课(恰过饭)的人。在饭桌上见到了蔡队 /se

吃完饭后,还是决定进城走走。刚好 installb 也有进城的意愿,于是我们两人便结伴而行,一块去了趟外滩。

得知 installb 也很久没来过外滩,好像也不算是个非常惊讶的事实。对于本地人来说,他们常常要面临更多现实的生活压力(中学生就更不用说了),这也让他们很难抽出时间来闲逛。对于外滩这种更多被游客占据的地方,似乎也很难提起本地人前往的意愿。

我想起了中学时期的自己。当时为了搞 OI,为了补课,别说周末了,就连长假也常常在机房或是教室度过。小时候还曾经参加过周边山区的徒步一日游,到后来就没怎么去了。疫情前生活就已经几乎过成了两点一线的样子。每天见到的,都是同样的人,做的都是同样的事,看起来没有什么波澜,如同云天明童话中的无故事王国一般。

也正是因为此,我非常珍惜每一次外出比赛的机会。出门远行,意味着遇见新的人,发现新的机遇,参与到新的故事当中。这也许就是 2019 年那几场线下比赛至今为我念念不忘的原因吧。体验过那样的感觉,就再也回不去了呢。

周六晚上的外滩,人非常多。我不知道这里面有多少是外地的游客,有多少是本地的年轻人。

在外滩,这边是租界时代留下的历史建筑,另外一边,则是现代化的浦东陆家嘴。说实话,这样的对比,再加上晚上的灯光,嘈杂的人流,外滩的历史气息,似乎削弱了几分。

走到了苏州河汇入黄浦江的地方,我们转向往内陆走去。外滩的嘈杂渐渐在耳边消失,上海的历史感,对我而言才渐渐显示出来。

走过苏州河上的最后一座桥——外白渡桥后,我们来到了苏州河的北岸。

在这样一个安静放松的环境下,我们两人的心境似乎也放开了不少。我们开始聊起各自的中学 OI 生涯,聊起大学。这些都是我在社交网络上有意避免提及的话题。

感觉在线上这样一个陌生的环境下,大家都有意识地将自己真正的快乐与痛苦掩藏起来,作为一种自我的保护。作为旁观者的我们,看到的更多是他人的侧面。在这样的环境下,感觉大家都不免变得扁平化,同一化起来。

我很少与其他人在线上私聊,也很少有人主动找我私聊。在各大群里聊天时,我好像就是一个被动接受信息,传递信息的机器人一般。只有信息的交换,却无情感的传播,更无思维的碰撞。

久而久之,一阵空虚感涌上心头,我感觉到生活似乎离我越来越远。以及,缺失了情感和思维的信息,真的有价值吗?

正因为如此,我越来越渴望线下与实体人类的接触。只有在线下的深度畅聊中,我才能把这些东西一点不少地找回来。

一路走到四行仓库,感觉时间也差不多了,就坐上地铁回去了。

生活还是得向前看啊。

生活还是得主动过啊。

坐地铁回去的路上,听说懵哥不幸打铁了,非常难过(不过那晚公布的线把打星队算上了,数据出现了点偏差,这里先按下不表)。

Day 2

早上第三次吃生煎。

华为挑战赛的赛题和 AHC 类似,都是优化性问题。这次的 B 题是个图论题,因此果断选它了。

优化目标的第一关键字是连通的点个数,第二关键字是边权,和生成树模型刚好对上。可惜自己码力不太行,很多细节没来得及调出来。

华为挑战赛结束后,不到一个小时就是闭幕式了。索性没去吃饭,在体育馆外等着能入场的时刻到来,顺带在门口捉群友继续聊天。

闭幕式的前半部分是华为的技术讲座,感觉讲了很久。

讲题解的时候发现 F 确实有一点带歪榜的成分在里面,事实上并不能说是非常好做的题。H 作为不太好写的搜索题,过的队没那么多倒也算很正常。

闭幕式上一些有意思的事情合集:

  • 懵哥是真的社交恐怖分子,一个小时前看他站在那和群友聊天,一个小时后看他还是站在那和同样的群友聊天。
  • 放的 VCR 小视频里闪过了一下 RUC 队「复旦栋梁」的队牌。
  • 懵哥队最后拿了 Cu 尾,于是各群都在喊懵哥回来拿奖(懵哥闭幕式和群友线下吹水到一半就跑出去打麻将(?)去了)。
  • 滚榜请了某个学校的教练来解说,这位教练的解说水准是在线的,然而因为没有提前准备的缘故,再加上后台滚榜的速度飞快,解说的嘴并没有那么顺畅,不过这位教练的口才还是制造了很多节目效果,让人印象深刻。
  • 主持人念一血名单,念到 K 题时,嘴瓢来了一句「清华大学 重生之我是菜狗」(其实真一血是垒球,但是打星);
  • 在公布校排前三之前,先发了最佳教练奖,结果有眼尖的群友发现 4-10 名顺序和对应的校排完全一致。结论是封榜封了个寂寞。
  • 菜狗队上台捧杯时,主持人:「你们为什么叫菜狗,你们明明一点都不菜!」

闭幕式结束后就是欢乐的华为之夜。去过去年 EC Final 的群友一路上都在倒苦水,吐槽大秦酒店的晚宴如何如何糟糕。

路上看到了「S20 外环隧道方向」的路牌。

落座后发现冷盘水平就非常在线,群友一致认为冷盘已经吊打了去年大秦酒店。后面还上了螃蟹啥的,感觉吃得非常过瘾!

前期没啥活动,再加上大家饥肠辘辘,基本上都在埋头狂吃。之后开始抽奖了,大家也都离开座位找群友线下激情吹水了,其实后来也上了不少好恰的菜,然而各群内的社交达人们,又哪有时间顾得上饭的。

有幸抽中了个三等奖,喜提一个蓝牙音箱。

对不少人来说,这次 EC Final 可能是算法竞赛生涯的最后一战了。此去一别,不知何时江湖再相见了,一想到这件事,内心不免感伤起来。

各位后会有期咯。

Day 3

睡了个好觉。

白天和 sleep__ 队三人一块吃了几天前没吃上的汤包,吃完之后就奔上海站去了。

(蟹粉面看起来是真的过瘾,不过贵也是真的。可惜我的肚子装不下两份饭,不然就不用做面和汤包的二选一选择题了。)

地铁上海站的 1 号线站厅和 3/4 号线站厅之间隔了一整个上海站的站场,指望中间的联络通道完全给地铁使用也不太现实,应该是永久性的虚拟换乘了。

回程坐的是 G16 次。发现 lk 也和我们坐一趟车,成功在候车室捉到 lk 了。

说实话这几天的经历真的如同梦境(虽然结果上很难说是美梦,这些事情另外开一篇文章讲),当列车停稳在北京南站,从出站口出来,坐上归程的地铁时,感觉自己才算是渐渐回到了现实。

2023 年 4 月 16 日

赛后复盘

待补。

碎碎念

另文公开。

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据