再见,acm

学校上周末和这周末有两场acm选拔赛,上周末因为自己回家没有参加。于是我在今天打算去试试水,看看自己是不是应该在打ctf的同时,把我一年没管的算法竞赛捡起来。

比赛时间是在12月26日下午1:30~5:00,一共有10道题。众所周知acm没有部分分,排名是按照做题时间与罚时来算的。我在这个下午AC了4道题,排名16/35,然而前14名才能晋级。

于是,这是我在大学打的第一场acm,也大概是最后一场了。

游记内容

当天上午

就写了两个板子,一个dijkstra,一个线段树。

dijkstra犯的几个错误(一年没写了,记不得也正常)

  • vis数组应该判断u,而不是判断v。
  • make_pair搞忘了,编译通不过。

线段树犯的几个错误

  • 忘记建树
  • 忘记pushdown怎么写

然而我并没有忘记把数组和懒标记开4倍。

午饭前得知可以带算法竞赛的书,也可以带纸质代码,可惜没时间准备了。

下午准备摸鱼。

当天下午

题目链接:https://vjudge.net/contest/474375

A题我本来想打表的,但是一看一群人瞬间就A了,再看看样例,规律很明显。直接$(n+1)/10$搞定,没有什么坑点。(CF评级800)

接下来看B题,B题看上去像道数学题,仔细一看是个背包。但是我已经有一年没写背包了,我早已经忘了怎么写。我去了趟厕所,想掏出手机复习一下,想想还是算了——反正我就是个摸鱼的。

在思考B题的同时,排行榜里已经有一堆人A了C题,但是我没管。直到我想了40分钟也没有一个时间复杂度正确的做法后,我终于暂时放掉了B题。

C题果然是个签到题,简单贪心,没什么好说的。(CF评级800)

然后G题A的人也比较多,然后我发现这道题是一眼题,要求的dijkstra我上午才写过,20分钟就A了。(CF评级1600)

思路就是对s和t分别求遍单源最短路,然后比较$min(dis1[i]+1+dis2[j],dis1[j]+1+dis2[i])$是否等于1。如果是那么加边就符合条件。

这个时候我rk12.

然后回过头来思考B题,经过了一个小时的挣扎后,我证明了自己的$O(m^2)$的做法是错误的,然后重新构思了一个$O(m^3)$的做法。

我之前的$O(m^2)$做法是把相同数的不同倍数处理成一个0/1背包,比如说有三个2,那么背包就为2 4 6.但是这样做,你选择的背包就有可能超过2的个数.比如说当m=12,这种算法会把2 4 6都选上,也就是你选了6个2,这当然是错误的。

我的改进方法是0/1分组背包,首先循环最外层是对组数进行枚举,中间层就是对相同数的不同倍数进行枚举,最后一层枚举背包体积。

我唯一做的一个优化就是如果在某一组结束之后已经枚举出和为0的方案,就直接break。

当m=1000的时候,这是个复杂度错误的做法,没想到我就刚好卡过了,1700ms/2000ms。

事后证明这个题要专门构造数据卡复杂度错误的做法也不是很容易,因此这种做法也是完全正确滴!正解的标签是dp,数据结构,组合数学和双指针,我完全搞不懂。(CF评级1900,还是比较高了)

这个时候我rk10.

然后我再看了下排行榜,发现F题和J题A的人比较多。F题让我想起了今年CSP的t1,而J题是个构造题,于是我义无反顾地选择了J题。

J题我花了半个小时写完了,交上去WA on case 5,佛了。找半天找不出错,于是我打算写一个spj。

因为spj和checker也有一年没有写过了,因此我花了一个小时才写好,结果自己写的spj又不知道哪儿出锅了,次长边的长度始终是0.

这个时候我rk14.

我觉得我不能再浪费时间在spj上了,于是我开始自己写数据自己肉眼判错。终于在比赛结束前15min发现了一个错误,用了5min改好,再次提交。

结果还是WA掉了。

剩下10min我躺平了,我看到我从rk14掉到了rk16,接受着自己算法竞赛就地退役的现实。

像上次强网杯那样的晋级奇迹应该不会再发生了吧,毕竟有10个人都能A掉四道题。

事后

稍微有一点可惜,因为F题也是一道贪心,CF评级是1500,比J题的1600还简单一点,有一点亏。

关键是J题我判定的特殊情况(d=h)中,有一类特殊情况中的特殊情况(d=h=1),不能使用这种我10min中前的修正方法判定。更坑的事情是,d=h=1的情况在我之前的代码是完全正确的,导致我完全忽略了在这里翻车的可能。

只不过——

听acheing(rk2)说,选上的人要补之前的算法作业。我认为,即使我侥幸进入了前14名,由于学校的代表队也就那么几个人,自己也就是个打酱油的,没必要在acm队里面瞎参合。

所以这究竟是一种幸运还是不幸呢?或许我就差那么一点进队,大概也是一种天意吧。我更应该干的事情是学好自己的专业,而不是尝试“脚踏两只船”,把自己弄得太疲惫。

所以——

さようなら,acm