AtCoder Regular Contest 173
| ID | Difficulty (0-5) | Topic | Status | Code |
|---|---|---|---|---|
| A | 1 | Binary Search, Math | Solved | A.cpp |
| B | 1 | Greedy, Boyer–Moore | Solved | B.cpp |
| C | 3 | Conclusion, Brute Force | Upsolved | C.cpp |
| D | 3 | Constructive Algorithms, Negative Cycle | Upsolved | D.cpp |
| E | ||||
| F |
B - Make Many Triangles
给定二维平面上的 $n$ 个点，每个点最多用一次，问最多能形成多少个不退化的三角形？
找出共线最多的点数 $x$ ，每次可以用 $x$ 中的两个点和外面的一个点构造，如此迭代。
所以答案是 $\min(\lfloor\frac{n}{3}\rfloor,n-x)$ ，复杂度瓶颈是求出共线最多的点数。
暴力是 $O(n^3)$ 的，以每个点为中心进行极角排序是 $O(n^2\log n)$ 的。
如果使用 Boyer–Moore 投票法，复杂度降低为 $O(n)$ 。
具体就是维护一个 stack，每次来一个点检查：
如果 size < 2，那么直接把这个点加入；
否则判断栈顶两个点和当前点是否能形成三角形，如果可以就弹出；否则把这个点加入。
最后如果 size < 3 那么答案就是 $\lfloor\frac{n}{3}\rfloor$ ；否则检查一遍，和当前栈中的点所共线的点数即可。
证明过程和 Boyer–Moore 投票法一致，如果存在超过 $n-\lfloor\frac{n}{3}\rfloor$ 的 $x$ ，那么最终它一定会被剩下来，因为每次形成的三角形最多占走 $x$ 中的 $2$ 个，而算法最多生成 $\lfloor\frac{n}{3}\rfloor$ 个三角形并不足以消耗完 $x$ 个共线的点。
C - Not Median
给定一个排列 $p_1,p_2,\dots,p_n$ 。
对每个 $p_i$ 找一个最短的包含它的奇数长度的区间，满足 $p_i$ 不是中位数。
对于 $p_1,p_n$ 边界的特殊情况，先用 $O(n)$ 的时间把答案求出来。
否则考虑 $p_{i-1},p_{i+1}$ ，考虑其和 $p_i$ 的大小关系，如果相同的话答案显然是 $[i-1,i+1]$ 。
否则向两侧分别看，如果和 $p_i$ 的大小关系一直是交替的，那么一直会让 $p_i$ 是中位数。
考虑找到最大的 $L<i$ 满足 $[p_L>p_i]=[p_{L-1}>P_i]$ ，同样找到最小的 $R>i$ 满足 $[p_R>p_i]=[p_{R+1}>p_i]$ 。
对于 $L\le l\le i\le r\le R$ 的所有奇数长度区间 $[l,r]$ ，都会让 $p_i$ 是中位数。
如果 $l=L-1$ ，容易发现包含 $i$ 后第一个奇数长度的区间一定不是 $p_i$ 为中位数，同样对 $r=R+1$ 。
因此答案就是这俩对应的区间长度的 $\min$ 。
维护每个位置和 $p_i$ 大小关系的符号，按照 $p_i$ 从小到大的顺序求答案，每次只有两个位置的符号会有改变。
然后用 set 维护相邻符号相同的位置即可，每次修改也只会有两个位置在 set 里的情况会改变。
这样总复杂度是 $O(n\log n)$ 的。
继续分析，先判断掉答案为 $[i-1,i+1]$ 的情况后，暴力的搜索 $L,R$ 的总复杂度是对的。
考虑所有需要搜索的位置分别为 $i_1,i_2,\dots,i_k$ ，我们有性质每个 $i$ 一定是 $[i-1,i+1]$ 的中位数。
考虑对于其中某个 $i_j$ ：$p_{i_{j-1}}$ 关于 $p_{i_j}$ 的大小关系一定和 $i_{j-1}-1,i_{j-1}+1$ 中至少一个一致。
对于右侧有同样的分析，因此对于 $i_j$ 我们有 $L\ge i_{j-1},R\le i_{j+1}$ ，这样所有的 $R-L$ 的和是 $O(n)$ 的。
D - Bracket Walk
给一个强连通图，每条边上都有一个左括号或右括号。
是否存在一个回路，过每条边至少一次，并且沿着路径记下来的括号序列合法。
数据范围：$n\le 4000,m\le 8000$
我们把 ( 看作 $+1$ ，把 ) 看作 $-1$ ，则括号序列合法对应于：总和为 $0$，且任意前缀和 $\ge 0$。
结论 $1$ ：如果一个回路总和为 $0$ ，总是可以调整成合法的序列。因为回路可以任选起点，所以沿着回路找到前缀和最小的点设置为新的起点，这样任意位置前缀和一定 $\ge 0$ 了。
结论 $2$ ：如果图中有正环负环存在情况相同则有解。
- 如果同时不存在：任一回路和都是 $0$ ，其中包括某个经过所有边的，因此答案存在。
- 如果同时存在：如果找到了一个经过所有边的回路和为 $+x$ ，找到的负环和为 $-y$ ，那么把 $+x$ 重复 $y$ 遍，再把 $-y$ 重复 $x$ 遍接在一起就可以得到和为 $0$ 的回路。反过来做法类似。
- 如果只存在一种：假设图中只存在正环，并且假设存在答案。因为答案包含所有边，我们把找到的正环中的边从中移除，回路中剩余的部分会分成若干段。考虑删掉的环中相邻的两条边如果在答案中没有连续使用，说明在中间的这个点处一定进来一次出去一次，不妨就这样把这两次连起来。这样所有的断开的位置都能找到一个配对的，剩余的路径会形成若干回路，并且他们的和是负的，这说明其中至少存在一个负环，与假设矛盾。
Bellman-Ford 判断图中是否存在正环/负环即可，正环可以转化成边权取反的负环。总复杂度 $O(nm)$ 。
AtCoder Regular Contest 173