解説

解説動画まんまです。

二分探索問題です。

問題の条件の、

a < b + c
b < c + a
c < a + b

というのは三角形の成立条件ですね。

3つの棒を選んで、それでいくつ三角形を作れるかという問題ですが、便宜上、選んだ3辺のうち最も長い辺をcとします。

単純な方法で求めるならば全探索で、a,b,cそれぞれでループ（3重ループ）回せばよいですが、それだと $O(N^3)$ でTLEします。

しょうがないので、aとbを固定して考えてみます（aとbについてforループで回します）。

与えられた棒が 2 3 4 6 6 7 10 とします。これをリストに入れて予めソートしておきます。

今、a=3, b=6 とすると、

2	3	4	6	6	7	10
	a		b

a + b = 9なので、a + b > c より、cは9未満になります。

2	3	4	6	6	7	10
	a		b	○	○

上記の○の数を数えていけば、答えは求まります。

ここで問題となるのが、上でいう「7以下」という境界をどう高速に求めればよいのかということですが、これは二分探索で高速に求まります。

f:id:takeg:20191122214936j:plain

コーナーケース

特になし

実装

# -*- coding:utf-8 -*-
import bisect

def solve():
    N = int(input())
    Ls = list(map(int, input().split()))
    Ls.sort()

    # O(N^2 * logN)の全探索で解く
    ans = 0
    for a_i in range(N):
        for b_i in range(a_i+1, N):
            c_i = bisect.bisect_left(Ls, Ls[a_i]+Ls[b_i])
            if c_i > b_i:
                ans += c_i - b_i - 1
            else:
                pass

    print(ans)

if __name__ == "__main__":
    solve()