2022-04-18 ABC248 E - K-colinear Line を解いた
ABC248 : AtCoder Beginner Contest 248 E - K-colinear Line を解いた。
解いたときに考えたことを書く。本番では解けなかった。
問題: https://atcoder.jp/contests/abc248/tasks/abc248_e
K 個以上の点を通る直線が何本あるかを求める。
K = 1 のときはいずれかの点をひとつ選べば無限に直線があるので Infinity 。
そうでないときは適当な 2 点を選んで直線を引き、そこからさらに 1 点を選んで線上にあるかを判定すれば良い。 O(N^3) なので間に合う。
ここからがまずかった。重複して数えているかを判定するために BTreeSet を使ったのだけど TLE した。解説では二次元配列を使って二点を通る直線が使用済みかを管理していた。
解説: https://atcoder.jp/contests/abc248/editorial/3792 提出: https://atcoder.jp/contests/abc248/submissions/31084965
今日のコミット。