Difference between revisions of "AtCoder Grand Contests"

From EOJ Wiki
Jump to navigation Jump to search
 
(7 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 259: Line 259:
 
* T: Tried
 
* T: Tried
 
* R: Read
 
* 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 ===
 +
 +
坑。

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

坑。

Retrieved from "http://acm.ecnu.edu.cn/wiki/index.php?title=AtCoder_Grand_Contests&oldid=2640"