ベスパリブ

プログラミングを主とした日記・備忘録です

ABC 143: D問題の解説 (Python3)

問題: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重ループ)回せばよいですが、それだと 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()

計算量は O(N^2 logN)です 。