ABC 422

AtCoder Beginner Contest 422

ABC题没什么好说的，签到题，但是C卡了我好久

主要讲一下E

E - Colinear

这是一道随机化搜索的题目，显然不可能尝试每两个点构成的直线是否满足要求，其时间复杂度是 $O(N^2)$ 但是随机找两个点都不在直线上的概率显然约等于 $\frac{1}{4}$ 。因此我们尝试 $T$ 次，能够通过的概率是 $1-\frac{1}{4^T}$ 只要 $T$ 够大就可以AC。

通过判断其他点是否在挑选的两点连成的直线上复杂度是 $O(N)$ 因此总复杂度是 $O(TN)$ 。$T$ 取适当大小即可。

官方题解：Editorial

---

说在最后

感觉打ABC有点道心破碎了，自己有点太水了……

这还是第一次碰到随机化搜索的题目