djwj233 的博客

djwj233 的博客

AtCoder Contest/VP 记录

posted on 2021-10-09 19:33:41 | under 计划 |

这个菜鸡的 AT 记录。

由于 CodeForces 时间太反人类,所以应该不怎么会打,大多时间可能会打 AtCoder。

由于菜,所以这里的比赛范围涵盖 ABC/ARC/AGC。

用 $\color{green}\Delta$ 表示 contest,$\color{Blue}\Delta$ 表示 VP。

$\color{Green}\Delta$ ABC 220

记录

拿了 Rank 157,performance 2317

第一场 AtCoder!!赛时写出 ABCDEF,然后看到 H 是个 NP-Hard 就弃掉去写 G,然后被卡精度了

ABCD 是思博题,E 有点意思,F 是个经典题。

赛后看到这个 sb 出题人写:

When using decimal types, be very careful of the computational errors.

For this problem, we think it would be safer to use only integer types.

还有:

We can either divide into cases, or treat lines in a form of $ax+by+c=0$ instead of $y=ax+b$.

肺直接气炸了!!!

H 是折半搜索,确实也没时间写。

最后 Rating:$0,\textsf{unrated}\color{black}\to\color{green}1117,\textsf{5 Kyu}$。

补题

题是不可能补的,这场太垃圾了,狗都不补。

总结

  • 有些几何题 tmd 会卡精度,要防着点。
  • 看到一题像是 NP-Hard,$n$ 范围是 $40$ 可以想到折半搜索。

$\color{Green}\Delta$ ABC 222

记录

拿了Rank 238, Performance 2130,感觉这场难度偏高。

赛时写出 ABCDEF,永远只能写六题,然后不会做 G,这是自己菜。

ABCD 比较简单,不过感觉不知道比 ABC220 高到哪里去了(

正序开题有点吃亏,因为 D 比 C 好写,F 比 E 简单

写 C 写了五六十行,由于数组开小(只开到 $n$,没开到 $2n$)吃了一发罚时。

E 是一个有点难度的题,主要思路是算出每条边的贡献然后背包,由于没判掉

if( (tot+k)%2!=0 ) return puts("0"),0;

这种不合法的情况又吃了一发罚时,挺尬的。

F 场上写的换根 DP,正解还有一个转化模型再利用直径的做法,感觉十分 nb。

G 是一个数论题,赛时飞快地把通项式写出来,嘴巴道:BSGS!

然后转念一想,ABC 考 nm 的 BSGS 呢!!!

然后从多角度、多方面推了一车假结论,还是没想出别的做法。

最后发现题解里有一种做法就是 BSGS。。。

H 是个生成函数铜牌题

赛后看了一下难度,发现大多数题的难度都高于 ABC220

最后 Rating:$\color{green}1117,\textsf{5 Kyu}\color{black}\to \color{Turquoise}1477,\textsf{3 Kyu}$。

补题

  • Prob. G

场上有点 sb,以为这是个猜结论题。

注意到里面 $a_n=\dfrac{2}{9}(10^n-1)$,因此等价于求一个最小的 $n$ 使 $\dfrac{2}{9}(10^n-1)\equiv0\pmod p$。

注意到 $4\nmid 22$,因此 $\forall n\in \mathbb N^+,4\nmid a_n$。进一步,对任意 $4\mid p$,题目都无解。

由于式子里面有个 $2$,因此对 $2\mid p$,$p$ 的答案应该和 $\dfrac{p}{2}$ 一样,这是易证的。

这样我们就把情况都转化到了 $p$ 为奇数的状况,此时$$ p\mid \dfrac{2}{9}(10^n-1)\Leftrightarrow p\mid\dfrac{10^n-1}{9}\Leftrightarrow9p\mid10^n-1\Leftrightarrow10^n\equiv 1\pmod{9p} $$ 这已经可以用 BSGS 求解了,场上没敢用(

首先我们可以归纳证明 $5\nmid p$ 时无解,这样就一定有 $\gcd(9p,10)=1$ 了。

注意到这和欧拉定理的形式$$ \forall \gcd(9q,a)=1, a^{\varphi(9p)}\equiv 1\pmod{9p} $$ 很像,因此我们猜想答案一定是 $\varphi(9p)$ 的一个约数,事实上这是易证的。

因此我们枚举 $\varphi(9p)$ 的约数逐一快速幂判断即可。

时间复杂度 $\mathcal O(T\sqrt{n}\log n)$。

  • Prob. H

生成函数不可做题。《新 概 念 A B C》

总结

这次主要失误在两发罚时,以及没有搞出 G。

  • 永远不要把数组开小!!!
  • 树上一切最长路相关问题都可以考虑直径。
  • 面对 $a^x\equiv 1\pmod{b}$ 的问题可以用上面那个结论而不是 BSGS。

$\color{Green}\Delta$ ARC 128

记录

拿了 Rank 199, Performance 2263

场上过了 ABC,D 没调出来(悲)

A 好像可以贪心,不过场上用对数写的 DP;B 不是很难搞,讨论一下模 $3$ 的余数即可。

C 想了好长时间!!1 最后发现结论是分成三段即可

D 是一个憨批普及组 DP 题,考虑到一段区间不合法当且仅当它含有连续两个相同或者是一个极长 $\texttt{ababa...}$ 的串,然后没调出来,真拉。

最后 Rating:$\color{Turquoise}1477,\textsf{3 Kyu}\color{black}\to \color{blue}1692,\textsf{2 Kyu}$。

补题

  • Prob. D

直接 DP。记 $dp_i$ 为以 $i$ 结尾的种类数,大力分讨再转移。

  • Prob. E

场上都没看过(悲)

看不懂题解,算了/dk

  • Prob. F

银牌题,不会。

$\color{Green}\Delta$ AGC 055

记录

拿了 Rank 205, Performance 2233

场上过了 AB,其中 B 问了 cmll02

A 先考虑只有 $\texttt{AB}$ 两种字母分成两段的做法,我们发现可以把字符串从中间劈开,取左边 $\texttt{A}$ 右边 $\texttt{B}$,右边 $\texttt{A}$ 左边 $\texttt{B}$。

然后就启发了正解分三段的解法。

B 就是考虑到 $\texttt{ABC,BCA,CAB}$ 都是一个像滑块一样可以滑的东西,于是我们删掉所有的

刚开始没注意到 $\texttt{ABABCC}$ 这种能删光,于是一直挂着

CD 都不会,EF 没开,听说 E 直接 Unavailable

最后 Rating:$\color{blue}1692,\textsf{2 Kyu}\color{black}\to \color{blue}1809,\textsf{1 Kyu}$。

补题

C 的这个 Editorial 又长又臭,弃了。

D Bold,E Unavailable,F Gold,我还补个锤子。

Anton 给爷爪巴!!!

$\color{Green}\Delta$ ABC 226

记录

打得巨拉,只有Rank 373, Performance 1947,甚至没上 $2000$(悲)。

赛时通过 ABCDE。

ABCDE 都是萌萌题,开场后 30min 都切光了。这时候开了 F。

发现这个 F 十分不好搞,于是打表 OEIS,但是找不到。

大约 60min 的时候借助 Peter 打的表搜到了 OEIS,此时 cmll02 和我说 G 是个白给题。

于是我花了 20min 左右去打 G 的贪心,打到心态爆炸回来写 F。

这时又有人说 F 暴搜能过,于是我又开始打暴搜,在 120min 过了 F,但是比赛时间只有 100min

最后 Rating:$\color{blue}1809,\textsf{1 Kyu}\color{black}\to \color{blue}1825,\textsf{1 Kyu}$。

补题

  • Prob. F

把排列看作一个置换,拆成几个循环后直接暴搜。

记第 $i$ 个循环的长度为 $siz_i(siz_i\ge siz_{i+1})$,$cnt_i$ 为 $i$ 出现的次数,$cur$ 为当前剩下的空档,答案即为:$$ \sum \dfrac{\sum(\binom{cur}{siz_i}siz_i!)^K}{\prod_{i} cnt_i!} $$

  • Prob. G

先每次匹配相等的物品和人,之后每次取出最大的物品和最大的人,然后匹配。

不会证正确性(

  • Prob. H

知识门槛不低(

我们枚举第 $K$ 大的变量介于哪两个整数之间,设为 $[A,A+1]$,然后暴力 DP,复杂度 $\mathcal O(mn^3)$。

具体地,记 $dp_{i,j,k}$ 为当前考虑了 $i$ 个变量,有 $j$ 个比 $A+1$ 大,$k$ 个在 $[A,A+1]$ 之间的概率。

那么答案就是 $k$ 个数中第 $K-j$ 大的期望。怎么算这个东西呢?

记答案不小于 $x$ 的概率为 $f(x)$,我们有:$$ f(x)=\sum_{i=m}^n \dbinom{n}{i} x^i(1-x)^{n-i} $$ 那么答案即为:$$ \sum_{i=m}^n\int_{0}^1 x^i(1-x)^{n-i}dx $$ 这东西叫 Beta 函数,有一车结论,据说答案能被化到:$$ 1-\dfrac{m}{n+1} $$

Code

总结

  • H 不会是我太菜。

  • F, G 之间的反复横跳和今年 CSP 本质相同,都导致了我浪费了大概 70min 左右的时间。

  • 以后比赛时不要乱开题!!!

$\color{Green}\Delta$ ABC 227

记录

打得更拉,只有Rank 658, Performance 1642,甚至没上 $1800$

开场 13 min 切了 ABC,后来一直卡在 D

然后一个多小时写了几个假做法,最后还是依赖 pbb 过的 D,最后发现 D 是 sb 二分答案

最后 Rating:$\color{blue}1825,\textsf{1 Kyu}\color{black}\to \color{blue}1789,\textsf{1 Kyu}$,下分力!!!

补题

赛时小傻逼,赛后大傻逼。

  • Prob. E

你发现 $|S|\le 30$,然后你用 DP 过了

个锤子,我不会!!!没事我们可以摆烂看题解。

woc,我看不懂题解!!!!!!区区 ABC 的 E!!!!

然后我们找到 Paulzrm 的记录,发现一种十分高明的做法:暴力 DFS!!!!!!!

  • Prob. F / G / H

扔了不做。

总结

自己太菜,啥都不会。