ABC143 D - Triangles (400)
棒をまず長さで昇順にソートする
i < j < kとなるように見ることで選び方の重複を防げる
愚直に3重ループを回すと
$ O(N^3)
で最悪ケースで
$ 10^{10}
を超えてしまう
ソートしたことで短い方の2本を決めると三角形が作れる棒の範囲は連続になるので二分探索できる
$ O(N^2\log N)
になるので間に合う
問題:
https://atcoder.jp/contests/abc143/tasks/abc143_d
提出:
https://atcoder.jp/contests/abc143/submissions/8028899
#ABC143
#400pt
#D
#ABC
#AtCoder
#O(N^2\logN)