Atcoder赛后反思

先贴上本人主页

• ABC347 \(\tiny\color{blue}1624\color{red}-24\color{black}=\color{blue}1600\)
• AGC066 \(\tiny\color{blue}1600\color{red}-21\color{black}=\color{cyan}1579\)
• ABC348 \(\tiny\color{cyan}1579\color{green}+114\color{black}=\color{blue}1693\)
• ABC349 \(\tiny\color{blue}1693\color{green}+67\color{black}=\color{blue}1760\)

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\)，有些连边是不需要的，有概率连到与目标解答案相同的状态，但比赛后才想到（