AtCoder Contest/VP 记录

这个菜鸡的 AT 记录。 [](https://atcoder.jp/users/djwj233) 由于菜，所以这里的比赛范围涵盖 ABC/ARC/AGC。 用 $\color{green}\Delta$ 表示 contest，$\color{Blue}\Delta$ 表示 VP。 ## $\color{Green}\Delta$ [ABC 220](https://atcoder.jp/contests/abc220) ### 记录 拿了 `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](https://atcoder.jp/contests/abc222) ### 记录 拿了`Rank 238, Performance 2130`，感觉这场难度偏高。 赛时写出 ABCDEF，~~永远只能写六题~~，然后不会做 G，这是自己菜。 ABCD 比较简单，不过感觉不知道比 ABC220 高到哪里去了（ 正序开题有点吃亏，因为 D 比 C 好写，F 比 E 简单 写 C 写了五六十行，由于数组开小（只开到 $n$，没开到 $2n$）吃了一发罚时。 E 是一个有点难度的题，主要思路是算出每条边的贡献然后背包，由于没判掉 ```c++ 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](https://atcoder.jp/contests/arc128) ### 记录 拿了 `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](https://atcoder.jp/contests/agc055) ### 记录 拿了 `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](https://atcoder.jp/contests/abc226) ### 记录 打得巨拉，只有`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](https://atcoder.jp/contests/abc226/submissions/27131850) ### 总结 - H 不会是我太菜。 - F, G 之间的反复横跳和今年 CSP 本质相同，都导致了我浪费了大概 70min 左右的时间。 - **以后比赛时不要乱开题！！！** ## $\color{Green}\Delta$ [ABC 227](https://atcoder.jp/contests/abc227) ### 记录 打得更拉，只有`Rank 658, Performance 1642`，甚至没上 $1800$。 开场 13 min 切了 ABC，后来一直卡在 D。 然后一个多小时写了几个假做法，最后还是依赖 pbb 过的 D，最后发现 D 是 sb 二分答案。 $\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 的记录](https://atcoder.jp/contests/abc227/submissions/27270776)，发现一种十分高明的做法：暴力 DFS！！！！！！！ - Prob. F / G / H 扔了不做。 ### 总结 自己太菜，啥都不会。 ## $\color{Green}\Delta$ [ABC 230](https://atcoder.jp/contests/abc230) ### 记录 打得还行，拿了 `Rank 95, Performance 2400`。 不过 zhouAKngyang 切题切麻了，devinwang 的号拿了 Rank 1 赛时过了 ABCDEF，感觉表现中规中举。 最后 Rating：$\color{blue}1789,\textsf{1 Kyu}\color{black}\to\color{blue}1903,\textsf{1 Kyu} $。 ### 补题 - Prob. G 这种枚举 $\gcd(i,j)$ 的，一般想到莫比乌斯反演，这样可以利用莫比乌斯函数将一个复杂的判断化成带一个系数的容斥。 我们考虑枚举当前数为 $x$，求 $x\mid i$ 且 $x\mid j$ 的贡献。这样式子就变成： $$ \sum_{x=1}^n\mu(x)\sum_{x\mid i}\sum_{x\mid j}[\gcd(P_i,P_j)\ne 1] $$ 怎么继续化呢？我们发现，对 $P_i$ 这一维也可以莫比乌斯反演。 设 $$ cnt(x,y)=\sum_{x\mid i,\ y\mid P_i} 1 $$ 那么就可以化成： $$ \sum_{x=1}^n\sum_{y=1}^n\mu(x)\mu(y)\left(\binom{cnt(x,y)}{2} +\binom{cnt(x,y)}{1} \right) $$ $$ =\sum_{x=1}^n\sum_{y=1}^n\mu(x)\mu(y)\dfrac{(cnt(x,y)+1)cnt(x,y)}{2} $$ 直接计算就是 $\mathcal O(n^2)$ 的，正确性没有问题。 考虑优化，我们预处理 $1\cdots n$ 中每个数的所有因数。枚举 $x$ 后找出所有的 $x\mid i$，枚举 $P_i$ 的所有因数计算出当前的 $cnt(x,y)$。 实际上，在计算时这个答案可以被同步算出。设当前 $cnt(x,y)$ 的值为 $t$，将 $t$ 加 $1$ 会使答案增加 $$ \mu(x)\mu(y)(\dfrac{(t+1)(t+2)}{2}-\dfrac{t(t+1)}{2})=\mu(x)\mu(y)(t+1) $$ 这个量，直接维护这个答案即可。[Code](https://atcoder.jp/contests/abc230/submissions/27680815) 最后我们分析一下复杂度。整份代码中开销最大的是这样一个操作： ```c++ fo(x,1,n) for(int i = x; i <= n; i += x) for(int y : fac[a[i]]) { // O(1) } ``` 每一个 $i$ 会被枚举到 $d(i)$ 次，会带来 $d(p_i)$ 的操作，总复杂度为 $\sum_{i=1}^n d(i)\times d(p_i)$。 由排序不等式，$\sum_{i=1}^n d(i)\times d(p_i)\le \sum_{i=1}^n d(i)^2$，且 $\forall i\in [1,n],p_i=i$ 时可以取到等号。 对上界： $$ \sum_{i=1}^n d(i)^2\le \max_{i=1}^n d(i)\times \sum_{i=1}^n d(i)=\mathcal O(n^{\frac{4}{3}}\log n) $$ 对下界： $$ \sum_{i=1}^n d(i)^2\ge \dfrac{(\sum_{i=1}^n d(i))^2}{n}=\Omega(n\log^2 n) $$ 然后就不会了/dk ## $\color{Green}\Delta$ [AGC 056](https://atcoder.jp/contests/agc056) ### 记录 记录 nm 呢，我 A 都没过，直接下大分。 不过这司马出题人为什么要放一个和正解八杆子打不着的垃圾样例啊！！！！ 最后 Rating：$\color{blue}1903,\textsf{1 Kyu}\color{black}\to\color{blue}1801,\textsf{1 Kyu}$。 ### 补题 - Prob. A 我们考虑 $n=6$ 的另一种构造： ``` ###... ...### ###... ...### ###... ...### ``` 我们发现这种构造对所有 $3\mid n$ 都成立，因此考虑模 $3$ 构造。 对 $n=7$： ``` ###.... ...###. ###.... ...###. ##....# ..##..# ....### ``` 对 $n=8$： ``` ###..... #..##... #....##. .###.... ....###. .##....# ...##..# .....### ``` 这样思路就很明晰了。 - Prob. C 一眼差分约束。我们定义前缀和数组为 $s$，那么由于要求前缀和最小，即要求跑出的 $s$ 尽量小，我们采用最长路求解。 但是这样直接跑 Dijkstra 是错的，因为有负边，跑 SPFA 时间又不允许，因此我们得尝试别的方法。 我们发现这个做法的瓶颈在于**等价关系被拆成两个方向的不等号**，这必然会导致负权边的出现。 考虑用前缀 $0$ 的数量减去 $1$ 的数量得到这个位置的 $s_i$，那么一个限制条件 $(l,r)$ 就等价于 $s_{l-1}=s_r$。 这就是等价关系了，我们可以用一个并查集划分出所有的等价类。考虑另一条限制，有： $$ |s_i-s_{i-1}|=1 $$ 事实上，由于同一个等价类中的奇偶性相同，且奇数点只会和偶数点连边，最短路跑出来之后**相邻两个点肯定不同**。 因此有 $s_i-s_{i-1}\ne 0$，我们可以直接把它转化成： $$ -1\le s_i-s_{i-1}\le 1 $$ 这样直接 01 BFS 就可以做到 $\mathcal O(n)$，而且我们要让 $s$ 尽量大。 ### 总结 - 构造题不要信小样例！！！ - 要多补补 AGC 的 A/B？ ## $\color{Green}\Delta$ [ABC 231](https://atcoder.jp/contests/abc231) ### 记录 赛时过 ABCDF，给了。只有 `Rank 723, Performance 1546`。 最后 Rating：$\color{blue}1801,\textsf{1 Kyu}\color{black}\to\color{blue}1765,\textsf{1 Kyu}$。 ### 补题 - Prob. E **从小到大**考虑每个货币然后 DFS。 - Prob. G 想到了拆开所有项算系数的做法，但是不会算那个系数qwq 设 $X_{i,j}$ 表示第 $i$ 个变量在第 $j$ 次有没有被选上，$X_i=\sum_{j=1}^t X_{i,j}$。有： $$ E\left[\prod_{i=1}^t X_i\right]=\sum_{(j_1,j_2,\cdots,j_t)\in [1,K]^t}E\left[\prod_{i=1}^t X_{i,j_i}\right] $$ 由于后面一式当且仅当 $j_i$ 两两不等时取非 $0$ 值 $\left(\dfrac{1}{n}\right)^t$，所以上式就是： $$ A_K^t\times \left(\dfrac{1}{n}\right)^t $$ - Prob. H 转化一下发现就是二分图最小权点覆盖，这东西要流。 加了一车虚点后妄想用 KM 过去，但是失败了（悲） ### 总结 - 要多练题； - ABC 中一题打了半天直接跳； - 多尝试推式子而不是找规律。 ## $\color{Green}\Delta$ [ARC 132](https://atcoder.jp/contests/arc132) ### 记录 赛时过了 ABC，只有 `Rank 413, Performance 1902`。 不会 D。 ### 补题 - Prob. D 很 nb 的一个题。我们把当前的字符串看成一条从 $(0,0)$ 到 $(n,m)$ 的路径，然后两个字符串中间的所有字符串就是夹在两条路径中的所有路径。 题目要让我们求一条使转折点最小，直接贪心即可。 ## $\color{Green}\Delta$ [ARC 133](https://atcoder.jp/contests/arc133) ### 记录 赛时过了 AB，只有 `Rank 667, Performance 1667`。 C 猜了个假结论，然后寄了。还是自己太菜！ ## $\color{Green}\Delta$ [ARC 138](https://atcoder.jp/contests/arc138) ### 记录 牛逼死了！！！ 赛时火速过了 ABC，发现 D 是原题，贺了一发，拿了 `Rank 20, Performance 3078`。 然后大家都不会 EF，赢麻了。 ### 补题 - Prob. E 考虑把 $a_i\ge 1$ 看成 $i\to a_i-1$ 的一条边，不难发现每个点至多一条出边，一条入边。 这样 $n$ 个点可以被看成若干向前的链，具体地，划分数量为 $\displaystyle {n\brace k}$。 这样我们发现每个长度为 $k$ 的下降序列等价于 $k$ 组嵌套的边。 记 $\displaystyle S(i)=\sum_{j=0}^i{i\brace j}$，我们可以直接列出答案为： $$ \sum_{i=k}^n\sum_{j=k}^{n+1-i} {i\brace k}{j\brace k}\binom{n+1}{i+j}S(n+1-i-j) $$ 题解就到这里。 这个做法怎么来的？如果题面中提到 $a_i\le i$ 且 $a_i$ 两两不同就可以考虑把这个条件放到图上。 如果没有想到图，$\displaystyle {n\brace k}$ 的结论是可以得出的。然后自然可以想到弄两行点，$k$ 阶下降序列就是 $k$ 条扭在一起的线。 这样如果直接做会有点问题：我们没法知道剩下 $n-2k$ 对点的相对大小关系，自然没法做。 解决方案就是连着那选的 $2k$ 个点的所在连通块全部拎出来统一计算，这就是上面这个式子了。