再见,算法竞赛! wu-kan

ICPC2019 徐州站游记

11 月 1 日周五

早上和二队、三队一起出发前往徐州。从一向稳重的总队长傅老板忘设闹铃开始,就注定了本次的徐州之行充满了演员互演。早饭是和队友和涵之小哥哥一起在金拱门买的「菠萝鸡扒麦满分」,吃进嘴里没有想象中的好吃。在广州地铁上和人群作了一番激烈斗争之后,一行人终于到了广州南站,@FlowBan 和去叫醒他的@HTL 也与我们会合。

由于前一夜睡眠不足的缘故,上了车之后的我直接开睡到下午一点,但是仍然很不舒服,因为同车厢内有幼儿园的阿姨带着好些小朋友。由于睡过了餐点,只好自己跑到餐车,花了六十块买了高铁上的盒饭…吃到了几乎是吃过最大的一只虾,有巴掌大小。

下午四点到达徐州。在高铁站,我的队友@reeeeein 开始了他的的第一次表演,在出站口处短暂的找不到票并且不知所措。徐州站的出站口竟然不可以刷身份证,一番周折后找到了检票员终于出了高铁站并坐上出租车,在快六点的时候到达酒店。这次我和三队王神@wcy1122 住一间。放下行李之后,一行人开始出去觅食。拖着一行人在酒店附近的商城跑了四楼,终于找到一家看起来不错的烧烤店。点了好多菜,平摊一下居然每个人只要三十多块,感觉挺实惠的。

烧烤

回酒店之后摸到队友@reeeeein 房间,帮他打了当晚的 CF 上分,顺便找到了弄丢的火车票。我从 C 题开始看,口胡了后四题的做法并且上手敲过了 D。结果还算凑合,终榜排名 168,我的队友一场 Rating+97 上了紫名(现在比我还高了 4 分,是我们小队的最高分了),这样我们队在区域赛之前有两个紫名了。然而感觉还是好菜啊…

11 月 2 日周六

早上九点醒了之后,看到同样这个点起来的@wcy1122 跑去酒店餐厅然后又回来,因为酒店的早餐只提供到九点。索性继续睡到十点半,然后集合去报道。

@zayin 他们去年也来了徐州站,因此这次在中国矿业大学就直接去报道的地方,没有额外耽误什么时间。领到了狗牌和衣服,之前来过的他们都吐槽参赛服和去年的一模一样。

在矿大的食堂吃了中饭。提供的餐卷是两荤一素,实际上阿姨给我打的菜感觉都是把各种肉和菜浇上酱油一起烧出来的。虽然我已经吃腻中大的食堂,但是一对比一下还是觉得本校食堂要好的多啦。

下午的热身赛一开始,@reeeeein 开始了他的第二次表演:把我们的密码条弄丢了。等我们终于在显示器背面找到密码条的时候,三道热身题已经全场过了两题了。一眼看到博弈题 B 和之前集训某场题目很类似,于是马上码过了这个题。A 题推错了复杂度然后 T 了两发,然后想了个线段树的做法能在规定时间跑完。然而赛后出来问了一下王神才想起来这是就是最简单的链剖,有线性解法…热身赛结束的时候,听隔壁东南大学队伍的交流搞会了最后一题 C 的做法,还是一道比较巧妙的构造题。

晚上和带队教练张老师会合,张老师带我们在昨晚的烧烤店的隔壁吃了一次鱼汤,相当鲜美。

鱼汤

这次回到酒店大概是八点多,希望早睡,于是在睡前把之前一直想看的《超新星纪元》从头开始看完了,十一点多丢下手机睡觉(对我来说已经是相当早睡了)。然而最后估计真正睡着估计要到一点多了…

11 月 3 日周日

早上还没有到闹铃的时间就自己醒了。心里有点紧张,跑去酒店餐厅吃了两个春卷一盘炒饭还有一杯橙汁。八点半的时候到达赛场,这时候马上去厕所,希望等下的比赛不要因为拉肚子误事。然而厕所只有两个坑位,其中一个还堵住了,体验非常差。终于在八点五十回到了机位,蓄势待发。

九点正式开赛,我们按照赛前商量好的,我从中间开始看题,我的两个队友从两头开始看。我一眼看到了 F,显然是可以打表过的一个题,马上敲了打表的程序并挂在后台,这时候@reeeeein 读到了签到题 C。队友交完 C 的时候我打表的代码也正好跑完,两题交上去都是 1A,这时候我们的排名在 15 名左右,非常顺畅。

看了一下全场的气球,A 大概是另外一道签到题,同时 B 感觉是可以找规律的一个题,因为样例已经给了 20 多组数据了(然而直到比赛结束这题也没几个队过的)。我在这边手算试了递推式的各种常见规律,暂时没有找到比较明显的,打算等队友过完 A 之后待定系数高斯消元试一试。这时候我开始看别的题,觉得 H(一个看起来是数据结构的题)、J(一个图论题)、M(一个树上的题)三题是比较可做的。

半个小时过去了,我们的排名跌到 30+,队友那边的 A 似乎遇到一些问题。这时候我有些慌,想起了去年青岛全队自闭卡 J 的情况。好在十点半左右他俩终于把 A 过了,排名又回到了 20 左右。这时候我和另一个队友@LALow 说了关于 M 题我的想法,不过代码复杂度略大。接下来的半个小时几乎开始起了争执,我觉得 M 题这个解法可做,他则认为会超时。不过,在手上没有题目可做的情况之下,还是决定敲一发来试试。在我们敲完这个题的框架的时候,边上@reeeeein 读到了一个数学题 E,并且和我说了一下题意,是一道解法非常明显的题,于是我们让开机位。

@reeeeein 开始了他的第三次表演,麻利的开始抄起了 Rho 大素数分解的板子。二十分钟多之后敲完这个题,然而连样例都没有过。这时候场上的队伍们看起来已经热身完毕,三题的队伍有一片了。我开始和@reeeeein 调这个题,而@LALow 则继续去想 M 题的细节,以便这题过了之后马上就可以接手。在查出各种小错(例如!=打成=!之后)之后,终于调过了样例,并且自己构造了几组数据都没有问题,一发提交之后却是RE

这时候隔壁上交的队伍已经过了五六题了(他们最后前十),而我们手上还抓着两个题,有点难受。于是打印代码,我和@reeeeein 各自检查一部分。我看的部分里某个地方在做乘方运算,然而数据范围是1e18,所以这里是有爆long long的风险的。换用了__int128之后再交了一发,可是结果仍然是RE

这个时候已经是十二点,比赛还剩两个小时,队伍排名掉到了 60 多。我打算如果最后一个小时如果这两个题还不能出的话只好赌一发的 H 暴力了。我们再次打印了 E 的代码,让开机位给@LALow 打 M,然而这时候才发现@reeeeein 的第四次表演:他的 E 是直接删了之前打的 M 的代码的,也就是说这题要全部重打。在队友们的爱 ♂ 抚之下,@reeeeein 承认了他演 ♂ 员的身份。

十二点四十,我们终于在本地复现了 RE 的问题,从而定位到 E 题代码的错:我的 Rho 分解里 MillarRabin 的检测素数有十二个,但这个演员@reeeeein 只抄了 11 个。十二点四十七分,提交的修改过后的 E 终于通过,我们的排到四题队伍最前面几名,总榜第 42,并且这个排名保持到了封榜。右手边的上交这个时候已经六七题,最顶上的北大一队已经八九题了。

这时候我们离目标的银牌已经很近了,但是还是不能松懈,开始三个人一起调 M。左手边的东南大学「该学英语了」和我们「中山大学_星云」的节奏也相当,封榜之后在 44 名,并且也在调 M。两边时不时露出会意的微笑:银牌已经近了,我们两边都是再过一题就是赚到。题目做法已经很明显,只剩下的代码实现了。一点五十分的时候,隔壁传来一阵欢呼,他们终于过了这个题;我们也找到之前推的式子里几个写反的地方,不过时间还是很紧张,以致于我们连本地样例都没有测就交上去了,299 分的提交。最后一分钟的提交在赛后快十分钟的时候才返回一个结果 WA,不过我们已经尽力了。

虽然封榜之后没有再过题,但是得益于我们这一场前期非常流畅的出题节奏和低罚时,我们的排名仍然在 53 名(银牌线是 85 名)。

银牌

比赛结束之后等了两个小时,终于拿到了奖牌,可以安心退役了~赛后二队三队们去了矿大的食堂,我在 KFC 请两个队友恰「泡菜牛肉脆皮汉堡」套餐,薯条堆了小半桌。

回到酒店,开始赶 AI 课的 Project…好肝啊,终于在十点半的时候跑通了样例,十一点半的时候写(Hu)好了报告提交到邮箱,开始了久违的补番辣~

11 月 4 日周一

早上一早,@reeeeein 开始了他的第五次表演,他又找不到回程的高铁票了。急忙和其他队说过之后,我们队三个人提前叫滴滴去高铁站的人工窗口看看能不能解决。然而在滴滴上,这个演员又双叒叕找到票了。

emmm。

好在我们没有在高铁站等多久就等到了其他几个队;我还在边上的按摩椅上坐了十分钟,稍微舒展了一下。

上了高铁之后,就想开始写这篇文章,写到这里的时间刚好是是十二点整了。回想,自己第一次接触算法竞赛还是在五年级,学校的蒋海老师带我用pascal敲下了第一行hello world;初中之后一度停止,再之后换 C++重新入门,高三才重新拿到 NOIP1=。直到上了大学才知道我之前的水平其实有多不值得一提。

虽然最后到达的终点和很多人比只是算是一个起点,但是算法竞赛这个老朋友总是在人生的关键时刻可以继续推我一把:中考凭借之前拿的普及组 1=进入了一中的实验班;自招时也继续靠着提高组 1=拿到了中大的加分。虽然,学院今年保研政策改成只有金牌才可以加分了,但是我仍然对平时集训和做题的时间怀以感激,它让我能够保持一个活跃的头脑和永远积极向上的力量,它还让我认识了一群有意思的人。感谢指导过我的每个老师,感谢和我组过队的每个队友,感谢向我祝福、支持过我的每个朋友。

有缘再会,算法竞赛!