競プロ
パ研合宿2020 第2日「パ研杯2020」 - AtCoder: D, E を解いた。
- D: ネタバレ→トポロジカルソートに帰着させる。そのままだと辺の本数が O(N^2) になってしまうので、動物用のノードを挟めばよい。←ネタバレ
- E: ネタバレ→直線と点は双対的な関係にあるので、点を直線とみなして、その直線の上に何個の点が乗るかわかれば ok、という言い換えができる。x の大きさで平方分割して、x > sqrt(100000) なら愚直に計算、x <= sqrt(100000) なら事前に a, b について前計算。←ネタバレ
