浙江大学ACM 2018 校赛游记

这次校赛,其实本来并没有打算报,毕竟高中noip爆0辣鸡省二退役的悲惨记忆还笼罩着我,且高二上学期退役以来,我就再也没有碰过算法竞赛的东西了。但是,快到报名截止日期的某一天,一位连部同学向我询问看什么书比较好,我突然就想来水二课分了。然后我拉上了@TJJ,而@TJJ同舍得@ZSJ在听说此事之后也加入了我们队伍。我们水平比较有限(一个高二退役,一个高一退役,一个没有经验),将队名取为「太不懂了」。我们的方针是做完阅读理解就行,不准备,不训练,随缘拿分,水水二课分就跑。 于是就到了校赛这天了,早上我开始临时抱佛脚地找了一下以前NOIP用的模板,然而正在准备打印的时候戏剧性的一幕发生了,@ZSJ看错了校赛地日期,以为是十几号进行,于是当天凌晨3点坐着火车去了上海。而比赛通知中写着队伍不齐不可入场,于是校赛看起来就不能参加了。当然因为本来就是想要来水一水,所以也没有对我产生太大的触动,于是我就拿着包去图书馆准备写微积分作业了。

在距离签到截止只有不到半小时的时候,事情再次发生了转变。林主席在计院群里催没有签到的人前去计算中心签到,我就顺手问了一句人不齐是不是可以比赛,结果得到了肯定的回答不仅如此其实就算你的位置上坐着别人也可以(当然这是不对的)……然后我就赶紧让@TJJ去计算中心签到,我就近打印了几十页模板,又回宿舍拿了lrj的白书。这时候竟然突然给了人一种比较认真的感觉(?)

然而很快到了机房我们的原型就显露出来了,上午这个时候本应该是在机房做一做热身赛的题目,但是@TJJ却在看了看题目以后就开始写数理方程,我也没看题目就在水知乎,将水二课分的丑恶姿态表现地淋漓尽致。然后到了十一点左右我们去临湖吃了个饭(奶油鸡并不好吃),然后各自回宿舍躺了会,到了十二点半就出来了(十二点半我在楼下等@TJJ的时候看到了@SJdl走出碧峰,这可能是我人品增加的重要因素)。

然后就正式入场,然而场内确实非常混乱嘈杂,放赛题的信封也没有密封,给人一种非常不正式的感觉。广播一直在重复「比赛正式开始之前不要动键盘鼠标,不要开机,关机,重启,不要开启其他电脑,不要在场内喝水吃东西,不要与其他队交谈」,然而好像并没有什么用。在得知了有高中生参赛以后,@TJJ就四周问「同学你们是高中生吗?」然而并没有的得到肯定的回复。

于是比赛就在混乱中开始了。一共10道题。上来先看了A题,就是统计矩阵里不在范围内的数有多少,很水的一道题。然而太久不写题手生的很,这么简单的一题也写了八分钟才完成。然后这期间有人过来放了一个气球,因为有一定延迟,所以我们在这时不知道气球是什么,并且发现每个桌子上都有一个气球,以为是每人桌子上一个气球用来装饰的。在这个过程中@TJJ读了最后一题,并且惊叹「这也太简单了吧,比NOIP简单多了」(然而结果就是只有这两道签到题比较轻松了)。于是又去切了最后一题,同样,非常手生,写完最后一题已经过去了11分钟了。然后过了一会又来了一个气球。然后@TJJ推测是一个题一个气球。然后@TJJ给我大概讲了B题C题G题和H题的题意,看到H题是个parser以后我就开始想做H题,但是突然发现没什么思路。然后我在听@TJJ讲G题题意的时候理解错了,以为是两个人一起走然后发现了一个O(N^4)的做法根本过不了,然后就去做C题了。

C题其实就是一个简单的模拟题,有对栈的push pop和把一个栈全部堆到另外一个上的操作,然后我选择了用数组模拟指针,然后发现结果非常不对。然后我点debug,然后devc++直接炸了。然后没法调试就很难受了,因为我太久不做,用 cout 调试这种技能基本已经荒废了。于是找了工作人员,工作人员找了另一个工作人员,另一个工作人员找了 yet another 工作人员。然后每个人过来点一次debug,然我的devc++炸一次。最后他们表示也不知道怎么回事,然后问我会不会用 gdb ,然而用gdb调试还不如直接用cout调试(此处应该有扶额兔子表情)。我期间还试了VS2017,结果辣鸡电脑直接卡炸了(这时候我没发现下面还有一个旧版本的不那么卡的VS)。于是我就强行看代码,但是怎么看逻辑都没有问题,然后观察输出,发现多了一个0,然后突然想起来是没有处理好把空栈移动到另外一个栈,我的做法会放一个多余的0在上面,然后处理这个问题以后样例就过了。然后提交,结果RE了。我看了一会也没看出什么问题,然后去了趟洗手间,然后突然想到我每个栈保留了一个guard元素,所以所需的数组大小实际上是元素数+栈数,然后改了以后就过了。这时候已经过去73min了。然后又来了第三个气球,这时候我们才明白了气球确实是过的题目数量。

然后在我做C题的时候,@TJJ继续看其他题,并且过程中惊叹过「哇这个好像机器学习」。然后我做完C题以后,他就说「我们做这个题会很有优势」。然后我们就开始做I题,I题的大意就是给你一堆名字,让你分类为日语名字和韩语名字,然后给了你6000条labeled data让你找规律(这里必须要称赞@TJJ的观察力非常敏锐,立刻想到了是一个找规律的过程,比赛之后得知很多人以为是以那6000条数据查表,不过这个题确实不是比较典型的算法竞赛题目的做法)。然后我就做了一个简单的根据元辅音判断(日语一个音节一个辅音,除了拨音n没有辅音韵尾),然后交上去就直接WA了。然后去看了那6000条数据,发现有很多韩语名字也满足这个规律,而且我忘了日语还有促音了。然后我想了想想起了韩语没f,日语没hu。然后又开了sublime,在个6000个数据里找规律,又加了一些ye je wo之类的日语不可能音节,最后剩下的误判的发现都是姓的长度小于等于3的韩语名字被判成日语了,然后特判以后又是一堆日语名字被判成韩语了。然后这时候再一观察发现其实日语姓长度小于等于3的但是音节长度并不为1,开头的都是元音,然后加了这一个限制后基本就只有少数不对的了。然后交上去之后就过了。于是I题就基本上正好做了一个钟头,到这里用了138min了。然后拿到第四个气球的时候就得到了称赞了。

然后@TJJ说「下面的都是比较难的算法题了」。不过这时候状态逐渐起来了,然后@TJJ说「G题贪心F题动规你想做哪个?」然后我就开始做F题了。然后才发现之前理解错了题意了,然后开始写状态转移方程,然后发现这其实是是个变形最短路,然后再一看每条路的长度都是1,于是其实就是一个简单的BFS(此处应用扶额兔子表情)。然后就开始写BFS,然后太菜了样例过不了,调试不了,最后发现是把信号灯分别垂直走和横着走写成了上右走和下左走,然后改了以后就过了。然后这时候已经封榜了,然而我们并不知道还有封榜这回事,看到榜上一直显示pending感觉很困惑,以为是TLE。然后过了一会又来了一个气球才打消了我们的疑惑。

然后最后做F题,这时候只剩下不到一个小时了。然后@TJJ说应该先把每个排序,然后这也每个都是顺序拿的了。然后我想了想贪心或许不行,然后就按照普通背包的思路写了个f[a][b][s]代表第一个拿了a件,第二个拿了b件,剩余空间s的最大值。然后发现这是个2000*2000*10^7的数组直接炸了(这时候又智障了)。然后我就开始想暴力,发现是2^4000,然后我开始想贪心行不行,结果证不出来。然后这时候只剩下30min了。然后我突然发现前面的s可以通过总空间S和a、b计算出来,然后发现就是2000*2000了。然后不到30min开始写代码,然后我连sort都不会用了,边界条件开始也没有写好。然后还剩5min的时候,样例终于过了。然后交上去WA,然后我想了想把int都改了long long,然后交上去TLE。这时候只剩下2min了,然后我开始写快速读入,结果写了一半看到了下面有两个没用的memset,然后停止了写快速读入,去掉了memset,然后最后不到1min的时候交上去最终AC。然后比赛就结束了,结果第六个气球没来得及给我们。然后我们就出去,然后我们看到很多人拿了气球,然后我们又走了回去,然后从地上的气球里捡了一个放到了我们的杯子里,拍了照,走了。

于是最后的结果就是水了6道题,最后校内排名11,就水一水来讲还是挺不错的。然后学军再次吊打我校,成功屠榜,学军中学附属大学坐实了。记得去年有人在知乎上说「就当提前和清华校队比试一下了」。