Atcoder赛后反思

先贴上本人主页



ABC347 \(\tiny\color{blue}1624\color{red}-24\color{black}=\color{blue}1600\)

蓝名保卫战,极限 1600

C 题还是有些思维难度的,最后才做出来,但是不够简洁

E 题忘开 %lld 喜提罚时

D 题最难评,又 WA 又 RE,最后如果输出不符合条件就输出 -1 才过

F 题原题,但是不会(

赛后发现就是一个二维前缀和 + 二位前缀max,还是挺简单的

G 题不会

赛时打的太急了,罚时太多,速度也被拖慢了,同分的最高 performance 有 2000+,还是代码实现不够快和准

AGC066 \(\tiny\color{blue}1600\color{red}-21\color{black}=\color{cyan}1579\)

E 题原题,还抓了一个抄题解的

A 题还是挺水的,只是没想到从奇偶性的角度来想,题解给的是 \(O(N ^ 2 D)\) 的做法,但是有更优且更简单的做法 \(O(N ^ 2)\),但是没想到,还是考思维。

B 题有点愚人节,python 语言优势很大(自带高精度),用几个 \(5 ^ x\) 拼起来多随机几次就完了,难绷(

蓝名没了 /ll

ABC348 \(\tiny\color{cyan}1579\color{green}+114\color{black}=\color{blue}1693\)

performance 2300+ 祭

0罚时切 A ~ F,让我又想起了那场似的 rated

F 题听说比较水,暴力 + O3 可过,但是我用 bitset \(O(\frac{N ^ 2 M}{\omega})\) 也过了(

G 题决策单调性优化板题,原题两道:here & here (但我不会)

upd on 2024.4.14 : G 题改出来了,应用单调性还是比较简单的,但是难在证明

ABC349 \(\tiny\color{blue}1693\color{green}+67\color{black}=\color{blue}1760\)

A ~ D 都比较顺畅,D 题盲猜 \(\text{lowbit}\) 喜提机房一血,E 题没开 long long 喜提一发罚时与机房一血

然后就坐着与 F & G 干瞪眼,F 先是用 cdq 尝试水分,后来将不是 \(M\) 因数的删掉了,还是不行

最后发现 \(M\) 最多有 \(13\) 个因数,直接 \(O(2^{13}N) \approx 1.638 \times 10^9\) 过了,AtCoder 神机

但是打得太急,F 题 7 发罚时,最后 4 发最离谱,一发没取模,一发取模太慢 TLE,一发将取模改成减法写错了,最后一发两处取模是copy的都错了,漏了一处没改(

\(\small \color{green}525 \color{red}(7)\) !!

G 题直接并查集开水,快 T 了就 No,过了一半的数据点

实际上还可以开随机化,因为对于 \(\forall i\),有些连边是不需要的,有概率连到与目标解答案相同的状态,但比赛后才想到(

ABC350 \(\tiny\color{blue}1760\color{red}-6\color{black}=\color{blue}1754\)

之前的总结写的太笼统了,更像是提要。刚好今天实在是打 emo 了,犯了很多离谱的错误,想写一篇个人直观的反思,从 ratingperformance 中跳出来,慢慢地审视整个过程。

A 题其实没有问题,可以直接A的,但是把 %03d 写成了 %02d 样例中也没有 ABC001,于是就挂了。

后来几道题一直很慌,越慌,越是想打快。越是快,就越出错。这很严重拖慢了整个切题的速度。C 题本来是没什么问题的,但是急着想过掉它,核心的代码几乎一半是错的,第一发直接罚时,这时心情也是很差了,很焦躁。后来逼迫自己冷静下来,又在草稿纸上画了几下,思路便逐渐清晰,于是便改对了。

到了赛点的后三题后,我其实刚刚松一口气,看到 E 题又自闭了,毕竟概率题上次就栽过,是ABC342F,这次又看到,心里一紧,只好先尝试 F 题。

F 题读完题后没多久就想到了 dfs,然而实现中还是有一些小错误,如 for 循环里更新 i 的话,它实际上还会 ++i/--i 一次,会跳过一个位置。好在没罚时。

切完 F 题后看了一下 G 题,一开始读错题了以为那个在线是假的,高高兴兴拿样例试水发现是错的。没办法,于是看 E 题,结果旁边的人看我蓝名快没了好心旁敲侧击,于是想到 DP,中途还有一个自己转移到自己的,想到了之前的一道题目虽然我没改出来,于是移项解方程即可。

一开始 \(10^{18}\) 我认为计搜是过不了的,因此打得不够坚定,还有一个变量重名调了很久,实现不够稳和准。开始是想着拿去水分的,但是直接过了,而且时间也很充裕(7ms)。赛后看题解,计搜时间复杂度实际上是 \(O(\log^3 n)\),但是主要问题是不会证明,对自己没有信心,于是犹豫了很久。

到了最后的 G 题,此时还剩下 20 分钟,已经机房内有人切了 G 题。出于对 G 题的潜意识压力以及前面比赛的表现,我此时已经基本失去思考能力了,脑子一片嗡嗡的根本想不到正解,打了一个根本就没概率的随机化过了一半,最后遗憾收场。

机房内同年级的有 4 个人过了 G 题,其中 3 人都是水过的,还包括两个代码相似的人。第四个大佬用了 splay

到这里,你可能认为 G 题还是有点难度的。但是,实际上,这也是我在比赛中犯的最后一个,也是最大的一个错误。

读完 G 题,其实不难想到如果维护好了森林中的每棵树有确定的根(具体是哪个节点与答案无关),并且维护好了每个点在其所在连通块中的朝向这个根的父亲,那么求解答案是 \(O(1)\) 的。比赛时这个念头在我脑海里一闪而过,但是很快就被否决了——原因很简单,这个维护过程直观上看是非常不可行的。后来,我转而去想 bitset 时间换空间,但一无所获。

然而,这就是问题所在——用暴力维护这些信息实际上的时间复杂度是正确的!因为每次连边的两个点都是在不同的连通块中,做完这次操作以后它们就会被合并,因此如果我们遍历一遍较小的连通块,总时间复杂度是 \(O(n\log n)\)!因此,这道 G 题出乎意料地短,甚至比我的随机化代码还要少。


写在最后:这次 ABC 可以看到除了少部分人,大多数人都没有取得很理想,甚至可以说糟糕的成绩。比赛结束后,我听到有人在机房里咒骂自己、题目和出题人的。还有人为了 rating 而闷闷不乐,诸如此类。但是有一点他们都错了,我们打比赛不是为了 rating 去打,不是为了成绩去打。以我为例,这次比赛我的 rating change-6,相对于之前 2200+performance,可谓是相当的差。但是,在这背后,是我被打乱的做题节奏,被扰乱的心态,使我过于激动的心情。这次比赛,暴露了我很多问题:代码实现不准不细心,读题不仔细,对时间复杂度的不敏感,对时间复杂度证明的不熟练,而这些,都为我提供了宝贵的经验,这远远不是几点 rating 所能给我的。之前还看到旁边的人比赛时一起讨论题目,其实也是十分不应该——如果人人都只在乎 rating 以至于无人在乎算法背后的玄妙,在乎它们的出处与归宿,那么 rating 早已失去它本来的意义了。希望各位在网络的各个角落的 Oier 都能保住自己的初心,守住心中的一寸净土,为了 OIACM,乃至 CS 的明天而砥砺前行。

热门相关:我的抖音太无敌   我写的书实在太毒了   甜蜜婚令:陆少的医神娇妻   剑道邪尊   侯门弃女之妖孽丞相赖上门