ABC143 D - Triangles - あっとのTECH LOG

問題原文

問題要旨

互いに区別できる $N$ 本の棒がある。 $i$ 番目の棒の長さは、 $L_i$ である。
これらの棒から３本の棒を使って、三角形を作る時、作れる三角形は何種類あるか。
ただし２つの三角形は、ある棒が一方にのみ使われているときに異なるとする。
また、三角形が成立する条件は、 (最も長い棒の長さ) < (それ以外の棒の長さの和) となるときである。

$1 \leq N \leq 3×10^{3}$
$1 \leq L_i \leq 10^{3}$

解法

重複なく数えられるようちゃんと気配りする。
棒の選ぶ順番に意味がないので、選ぶ棒の長さを $a, b, c$ として、 $a \leq b \leq c$ となるように選ぶことにする。

最も短い棒と、その次に短い棒を固定する。（これらの長さを $L_i, L_j$ とする）
すると、三角形が成立するような最も長い棒の長さは、 $L_i + L_j$ 未満であって、 $L_j$ より長いもの（これは自明に成り立つ）である必要がある。
そのような棒の数は、あらかじめ棒をソートしておいて、二分探索で数えることができる。
このとき、条件を満たすような棒であっても、 $j$ 番目より小さい棒はカウントしないこと。（a, b, c の index がそれぞれ i, j, (最も長い棒) となるようにする）

実装

下手に組み合わせ計算に走ると破滅するので、ぐっと堪えて楽な方法を探す。

from bisect import bisect_left
N = int(input())
L = sorted(list(map(int, input().split())))

ans = 0
for i in range(N):  # １番短い棒
    for j in range(i + 1, N):  # 真ん中の長さの棒
        ans += bisect_left(L, L[i] + L[j]) - (j + 1)

print(ans)

感想

i < j < (最も長い棒のindex) を常に意識する。