問題：AtCoder Beginner Contest 143: D - Triangles
公式解説PDF：https://img.atcoder.jp/abc143/editorial.pdf
公式解説動画：https://youtu.be/3U_N7zelnMM?t=2983
解説
解説動画まんまです。
二分探索問題です。
問題の条件の、
- a < b + c
- b < c + a
- c < a + b
というのは三角形の成立条件ですね。
3つの棒を選んで、それでいくつ三角形を作れるかという問題ですが、便宜上、選んだ3辺のうち最も長い辺をcとします。
単純な方法で求めるならば全探索で、a,b,cそれぞれでループ（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以下」という境界をどう高速に求めればよいのかということですが、これは二分探索で高速に求まります。
コーナーケース
- 特になし
実装
# -*- 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()
計算量はです 。
