AtCoder Grand Contests
大坑。
有意思的题会写题解。
Status
| # | A | B | C | D | E | F |
|---|---|---|---|---|---|---|
| AtCoder Grand Contest 001 | · | · | · | · | · | · |
| AtCoder Grand Contest 002 | · | · | · | · | · | · |
| AtCoder Grand Contest 003 | · | · | · | · | · | · |
| AtCoder Grand Contest 004 | · | · | · | · | · | · |
| AtCoder Grand Contest 005 | · | · | · | · | · | · |
| AtCoder Grand Contest 006 | · | · | · | · | · | · |
| AtCoder Grand Contest 007 | A | A | A | A | · | · |
| AtCoder Grand Contest 008 | · | · | · | · | · | · |
| AtCoder Grand Contest 009 | · | · | · | · | · | · |
| AtCoder Grand Contest 010 | · | · | · | · | · | · |
| AtCoder Grand Contest 011 | · | · | · | · | · | · |
| AtCoder Grand Contest 012 | A | A | A | A | A | · |
| AtCoder Grand Contest 013 | · | · | · | · | · | · |
| AtCoder Grand Contest 014 | · | · | · | · | · | · |
| AtCoder Grand Contest 015 | · | · | · | · | · | · |
| AtCoder Grand Contest 016 | · | · | · | · | · | · |
| AtCoder Grand Contest 017 | A | A | A | A | A | · |
| AtCoder Grand Contest 018 | · | · | · | · | · | · |
| AtCoder Grand Contest 019 | · | · | · | · | · | · |
| AtCoder Grand Contest 020 | · | · | · | · | · | · |
| AtCoder Grand Contest 021 | · | · | · | · | · | · |
| AtCoder Grand Contest 022 | A | A | A | · | R | · |
| AtCoder Grand Contest 023 | · | · | · | · | · | · |
| AtCoder Grand Contest 024 | · | · | · | · | · | · |
| AtCoder Grand Contest 025 | · | · | · | · | · | · |
| AtCoder Grand Contest 026 | · | · | · | · | · | · |
| AtCoder Grand Contest 027 | A | T | · | · | · | · |
| AtCoder Grand Contest 028 | A | A | · | · | · | · |
| AtCoder Grand Contest 029 | A | A | A | · | · | · |
| AtCoder Grand Contest 030 | · | · | · | · | · | · |
- A: Accepted
- T: Tried
- R: Read
Journal
7C
猜他拿完一个以后期望仍然是等差数列就赢了。（反正我是看了题解）
第 $i$ 段，分三种情况讨论，贡献分别如下（这一部分题解省略了）：
- $\frac{i}{2n} (d + (i + 1)x)$
- $\frac{1}{2n} (3d + 3 i x)$
- $\frac{2n-i-1}{2n} (d + (i-1)x)$
7D
跟多校的某个折线题（我记得有张图的）很像。搞清楚答案的形状之后，转移方程就是：
$f_i = min_{1 \le j \le i} \{ f(j - 1) + \max(2(x_i-x_j), T) + (x_i - x_{j-1})\}$。
max 的那部分可以用单调队列处理，中间的那部分维护一个单调增队列，弹出来以后更新一个全局最小值。最后答案就是两部分的 min。
12C
很容易想到二进制分解，不过太长了。
遂自闭。
题解中的构造方法是 $(p_1,p_2,\ldots,p_n,1,2,\ldots,n)$。这样的话前面和后面的部分的公共子序列会贡献 1。问题就转化成了构造一个排列使得上升子序列个数恰好为 $n$。
然后发明了一种假算法 WA 了，又自闭了。
题解是这样的：假设已经有 $1$ 到 $n$ 的某个排列，上升子序列个数是 $k$。把 $n+1$ 加在后面，可以得到 $2k$，把 $n+1$ 加在前面可以得到 $k+1$。然后递归构造就好了。
当然还有一个有趣的问题是这题的 SPJ 怎么写。(貌似是一个挺经典的 DP)
12D
首先如果 a 能和 b 换，b 能和 c 换，那么 a 就能和 c 换。所以只要把连通关系找到。
很容易想到一个东西越小它就越是 flexible。所以每种颜色最小的跟其他的连边；所有颜色中最小的跟其他颜色的连边。那么最小的里面稍大一点的可能还不能顺利连通；所以还要挑第二少的颜色连一下边。
题解似乎不是这么做的，看起来复杂得很。
12E
做了好几天，有了好几个 observation，但是最后还是看了题解（悲伤）。首先问题转化成：能否将 $x_1$ 到 $x_n$ 划分成若干个区间，使得每个区间内的东西相邻距离都不超过 $v_k$。对于固定的 $v_1$ 输出答案。然后我发明了一套树上乱搞的方法，自闭了。
题解是子集 DP。记录每种子集能覆盖的最大前缀和最大后缀。最后把第一个贴上，判一判就好了。写起来稍微有点痛苦。
17B
式子推错了，两次！捣鼓了好久。
17C
考虑如果最后要变成 $1$ 到 $n$ 怎么做：我们把所有数装在桶里，最后有几个桶是空的，答案就是几。
现在如果有 $k$ 个 $x$，就给 $x, x-1, \ldots, x-k+1$ 这些桶里都加 1。很容易看到，最后有几个桶是空的，答案就是几。
随便维护一下就好了，不需要数据结构。
17D
AGC 也出原题？
17E
很显然把拼图当成边建图，这个图有两部分，我们要将这个图分解成若干起点在左边、终点在右边的路径。
数据规模不大，可以网络流。左边有残余的点连 S，右边有残余的连 T，跑最大流，先检查是否满流。然后要想办法把可能剩下的一些环拼上去。发现只要检查图的连通性就可以（有边的点是否都跟 S 相连）。
题解是 $O(H)$ 的，显然想得更清楚。
22C
关键在于字典序最小。显然逐位确定。确定之后对后面的部分进行「乐观估计」，可行才往下搜，这样的 DFS 不会回溯。最短路复杂度 $O(n^3)$，总复杂度是 $O(n^4)$。
这个最短路挺有意思。
22E
坑。