AGC004
AtCoder Grand Contest 004
C - AND Grid
构造. ## D - Teleporter 图论构造, 结论显然. ## E - Salvage Robots
考虑移动Exit点和边界, 分析性质, 设计DP. ## F -
Namori
0%
AGC003
AtCoder Grand Contest 003
D - Anticube
- 直接将每个数的立方因子去掉,作为代表元素. \(O(A^{\frac13}/\ln A)\)
- 每个集合与其互补集合之间只能选择1个.
- 如何寻找互补集合?
- 对于\(p^3 \le 10^{10}\)的因子,暴力处理.
- 剩下的部分只能是\(p\),\(p^2\)或\(pq\)形式, 查表.
E - Sequential operations on Sequence
- 首先\(\{a_n\}\)可以变成单调栈.
- 考虑倒着处理问题, 每次把后缀加回前缀, 最后得到的数列就是每个数字的出现次数.
- 实现显然 \(O(Q\log Q\log N)\)
F - Fraction of Fractal
Educational Codeforces Round 119
Educational Codeforces Round 119
F. Bipartite Array
容易发现，二分序列一定可以划分成小于2个上升子序列。
由Dilworth定理，条件等价为\(LDS\le2\)。
考虑dp， 记录\(l=1\)和\(l=2\)的下降子序列中的最小的数。
得到\(O(n^3)\)做法。
WIP...
AtCoder Beginner Contest 231
Panasonic Programming Contest 2021(AtCoder Beginner Contest 231)
E. Minimal payments
Easy digit DP practice.
G. Balls in Boxes
Consider the Multivariable PGF of this problem:
\[ f=\frac{1}{n^k}\prod x_i^{A_i}\left(\sum x_i\right)^k \]
The term of the score, which is \(\prod _{i=1}^NB_i\), immediately implies the answer to the problem.
\[ E(score)=\left[ \frac{\partial^N f}{\partial x_1\partial x_2\dots\partial x_N} \right ]_{x_i=1} \]
We can notice that
\[ \frac{\partial }{\partial x_i}x_i^{m_i}\prod_{j\not=i} x_j^{m_j} \left(\sum x_i\right)^k =m_ix_i^{m_i-1}\prod_{j\not=i} x_j^{m_j}\left(\sum x_i\right)^k+kx_i^{m_i}\prod_{j\not=i} x_j^{m_j} \left(\sum x_i\right)^{k-1} \]
Let coef[n] be the coefficient of \(\prod x_i^{c_i}\left(\sum x_i\right)^n\),
we can easily process the partial derivative by an \(O(n^2)\) DP.
H. Minimum Coloring
The problem can be easily reduced to a weighted minimum edge cover problem on a bipartite graph.
Let's first choose the minimum cost at each vertices, and let it be \(C_u\).
Now we change the weight of each edge\((u, v, w)\) to \(w'=w-C_u-C_v\).
The answer should be \(\sum C_u-\) minimum cost matching of the resulting graph.
Since the new graph now have negative cost edges, we can solve the problem as follows: (from AtCoder editorial)
add a constant to make all weight positive, and subtract it accordingly on the minimum cost slope.
Alternatively, we may add an edge from S to T with capacity min(H,W) and cost BIG and find the minimum cost of flow min(H,W) to find the answer in the same way.
AtCoder Regular Contest 131
AtCoder Regular Contest 131
C. Zero XOR
结论：
\(2\not|n\)时，必胜。
\(2|n\)时，若存在\(XORSUM=A_i\)，则必胜，否则必败。
证明：
只需证明1即可。
转化：证明1，只需证明\(n\)为奇数时，游戏不会在恰好2次操作后结束。
若游戏在两轮后一定结束，则\(\forall A_i, \exists A_{p_i}\ s.t.\ S \oplus A_i \oplus A_{p_i}=0\)
则所有\((i,p_i)\)组成\(n/2\) 组。而必然剩余一组\(p_i=i\)，构成矛盾。
D. AtArcher
距离必定\(=d\)
中点必定在0附近
中点最多移动\(O(d)\)，而所有所属区间的变化数量为\(O(m)\)
线性扫描即可
E. Christmas Wreath
思路：先判定有解后构造/优先考虑特殊限制
有解条件
\(n \not=2(mod\ 3)\)
考虑如何满足条件2
如果每一个点的邻接边都同色，则条件2必然满足。
问题转化为：将\(1,2,3\dots n-1\)分成和相等的三组。
增量构造即可。
Educational Codeforces Round 118
Educational Codeforces Round 118
D. MEX Sequences
A subsequence is valid if and only if one of the following is true for any prefix.
\(\{b_1, b_2\dots b_k\}=[0,k]\). (expandable)
\(\{b_1, b_2\dots b_k\}=[0,k]\cup\{k+2\}\). (non-expandable)
We can maintain the number of type 1/ type 2 subsequences with \(\mathrm MEX = k\), while adding \(a_i\) accordingly.
E. Crazy Robot
elementary BFS practice.
F. Tree Coloring
The objective is hard to achieve directly. We can apply Inclusion-Exclusion Principle to simplify the constrains.
Let \(f(n)\) be the number of coloring that has at least \(n\) edges with \(c_{fa} =c_v +1\).
Then \(Ans=\sum_{k}(-1)^kf(k)\).
\(f(n)\) can be calculated using divide-and-conquer FFT from the equation below.
\[ f(k)=(n-k)!\sum_{u_1,u_2\dots u_k\in V}\prod_{i=1}^k|childs(u_i)| \]
time: \(O(n\log^2n)\)
space: \(O(n)\)
Deltix Round, Autumn 2021 (Div. 1 + Div. 2)
Deltix Round, Autumn 2021 (open for everyone, rated, Div. 1 + Div. 2)
E. William The Oblivious
solution 1: (dynamic divide and conquer / segment tree)
\[ \begin{aligned} Ans =& \min_{l\le r}\{S[0,l)\#a+S[l,r)\#b+S[r,n)\#c\} \\ =& \ S\#b+\min_{l\le r}\{S[0,l)\#(a-b)+S[r,n)\#(c-b)\} \end{aligned} \]
线段树维护区间最小前缀、后缀、答案即可。
solution 2: (DDP)
WIP
F. Interesting Sections
\[ Ans=\sum_{l\le r}[\mathrm{popcnt}(\min\{a_l\dots a_r\}) = \mathrm{popcnt}(\max\\a_l\dots a_r\})] \]
应用单调栈+线段树维护最大值个数。
time: \(O(n\log \max a+n\log n)\)
space: \(O(n)\)
G. A Stroll Around the Matrix
思路：先考虑静态问题，构造最优解/通过作差（微调法）将高维问题降维处理。
Codeforces Round #757 (Div. 2)
Codeforces Round #757 (Div. 2)
D2 - Divan and Kostomuksha
设计一维状态记录\(\gcd\)即可。不整除的数将自动排在后面。
\[ dp_n=\max_{p\ is\ prime} \{dp_{pn} +\#[a_i|n]-\#[a_i|pn]\} \]
time: \(O(n\log\log n)\)
E - Divan and a Cottage
线段树动态开点维护函数值。
因为题目中函数单增，故可以使用定位区间的方式确定要修改的区间。
time: \(O(n\log n)\)
space: \(O(n\log n)\)
AGC problems
Posted on
Edited on
Problem C
AGC038 C - LCMs
如果没有现成的数论函数来完成容斥，可以自己造一个！
let
\[ \frac1n=\sum_{d|n}{f(d)} \]
\[ \begin{aligned} \textrm{lcm}{(x, y)} =&\ \frac{xy}{\gcd(x,y)} \\ =&\ xy\sum_{d|x,y}{f(d)} \end{aligned} \]
\[ \mathrm{ans}(i)=\sum_{d|a_i}f(d)\sum_{j<i}a_j[d\ |\ a_j] \]
AGC040 C - Neither AB nor BA
将奇数位上\(A\rightarrow B\),将不能选\(AB\ BA\)转换成不能选\(AA\ BB\)。
结论：\(A\), \(B\)各不能超过一半。
AGC041 C - Domino Quality
大构造，人工智能。
AGC035 C - Skolem XOR Tree
大构造x2
根据样例提示，有\(\bigoplus_{i=1}^{2^k-1}i=1\)。
对于\(n=2^k\)，只有一个第\(k\)位出现，显然-1.
对于\(n \&1\)，将大于\(2^{\mathrm{31-clz(n)}}-1\)的部分按\((2k,2k+1)\)分组。
对于\(n \& 1=0\)，特判前三个数，其余类似处理。