Difference between revisions of "AtCoder Grand Contests"
(→Status) |
|||
| (5 intermediate revisions by the same user not shown) | |||
| Line 103: | Line 103: | ||
|- | |- | ||
! scope="row"|AtCoder Grand Contest 012 | ! scope="row"|AtCoder Grand Contest 012 | ||
| − | | | + | |A |
| − | | | + | |A |
| − | | | + | |A |
| − | | | + | |A |
| − | | | + | |A |
|· | |· | ||
|- | |- | ||
| Line 143: | Line 143: | ||
|- | |- | ||
! scope="row"|AtCoder Grand Contest 017 | ! scope="row"|AtCoder Grand Contest 017 | ||
| − | | | + | |A |
| − | | | + | |A |
| − | | | + | |A |
| − | | | + | |A |
| − | | | + | |A |
|· | |· | ||
|- | |- | ||
| Line 183: | Line 183: | ||
|- | |- | ||
! scope="row"|AtCoder Grand Contest 022 | ! scope="row"|AtCoder Grand Contest 022 | ||
| + | |A | ||
| + | |A | ||
| + | |A | ||
|· | |· | ||
| − | | | + | |R |
| − | |||
| − | |||
| − | |||
|· | |· | ||
|- | |- | ||
| Line 199: | Line 199: | ||
|- | |- | ||
! scope="row"|AtCoder Grand Contest 024 | ! scope="row"|AtCoder Grand Contest 024 | ||
| − | | | + | |A |
| − | | | + | |A |
| − | | | + | |A |
| − | | | + | |A |
|· | |· | ||
|· | |· | ||
| Line 260: | Line 260: | ||
* R: Read | * R: Read | ||
| − | = | + | = Journal = |
=== 7C === | === 7C === | ||
| Line 279: | Line 279: | ||
max 的那部分可以用单调队列处理，中间的那部分维护一个单调增队列，弹出来以后更新一个全局最小值。最后答案就是两部分的 min。 | 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 === | ||
| + | |||
| + | 坑。 | ||
Latest revision as of 12:30, 1 February 2019
大坑。
有意思的题会写题解。
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 | A | A | A | A | · | · |
| 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
坑。