ABC143 D - Triangles
備忘録
問題
回答
import sys import os import math import bisect import itertools import collections import heapq import queue import array import time # 時々使う # from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall # from decimal import Decimal # from collections import defaultdict, deque # 再帰の制限設定 sys.setrecursionlimit(10000000) def ii(): return int(sys.stdin.buffer.readline().rstrip()) def il(): return list(map(int, sys.stdin.buffer.readline().split())) def fl(): return list(map(float, sys.stdin.buffer.readline().split())) def iln(n): return [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)] def iss(): return sys.stdin.buffer.readline().decode().rstrip() def sl(): return list(map(str, sys.stdin.buffer.readline().decode().split())) def isn(n): return [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)] def lcm(x, y): return (x * y) // math.gcd(x, y) MOD = 10 ** 9 + 7 INF = float('inf') def main(): if os.getenv("LOCAL"): sys.stdin = open("input.txt", "r") N = ii() L = il() L.sort() ret = 0 for i in range(N): for j in range(i+1, N): c = L[i] + L[j] idx = bisect.bisect_left(L, c) if idx > j: ret += idx - j - 1 print(ret) if __name__ == '__main__': main()
考え方
3つ存在する変数のうち2つを予め固定してしまい、残りの変数を効率的に求める問題です。
- 回答概要
- 棒
a
と棒b
は全探索で固定してしまう - 棒
a
と棒b
で三角形を作ることが出来る棒c
は二分探索で求める
- 棒
まず、回答の方針を考えます。
3 <= N <= 2 * 10 ** 3
から、
棒a, b, c
をそれぞれ全て試す全探索を行った場合、
計算量はO(N ** 3)
となり、制限時間に収まらないと考えられます。
次に棒a, b
をそれぞれ全て試す全探索を行った場合、
計算量はO(N ** 2)
となり、残りの棒c
を効率よく求めることが出来れば、
制限時間内に収まりそうなことがわかります。
棒a, b
を固定した場合、
棒c
はc < a + b
を満たす必要があります。
このようなc
を求めるために二分探索を行ないます。
昇順ソートしたL
に対して、先頭から棒a, b
を決めます。
この時のc
はc < a + b
かつb
よりも右に位置する整数です。
そのため、二分探索でc
の挿入位置を求めて、
b
より右に位置し、c
の挿入位置以下の整数の個数が、
棒a, b
と三角形を作ることが出来るc
の個数になります。