binary search atcoder

Atcoder Beginner Content 143 D - Triangles

Atcoder Beginner Content 143 D - Triangles
Feb. 2, 2020, 1:52 p.m.

目次

問題

https://atcoder.jp/contests/abc143/tasks/abc143_d

解説

すべての辺の組み合わせを単純に調べると$O(N^3)$となり間に合わない.
なので、最後の1辺の決定を高速化して$O(N^2 LogN)$に収める.

長さに制約のある問題なので、すべての辺を長さが短い順にソートしておく.
AとBを決定するとCの辺のとれる長さの範囲が決定する.
この範囲に収まる長さのCの数をカウントすれば良い.
辺はソート済みなので、二分探索を2回行い、Cを満たす最小値と最大値を探しその間の要素数をカウントする.

計算量

$O(N^2logN)$

※AとBを列挙するために$O(N^2)$、Cを二分探索で探すために$O(logN)$

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#define MAX_N 2001

Int N;
vector<Int> L(MAX_N, -1);

void input() {
  cin >> N;
  loop(i,0,N) cin >> L[i];
}

void solve() {
  sort(span(L,0,N));  // sort edges by length asc

  Int count = 0;
  //O(N^2)
  loop(a,0,N-2) {
    loop(b,a+1,N) {
      Int min_c = L[a] - L[b] + 1;
      Int max_c = L[a] + L[b] - 1;
      // Binary search twice. O(2LogN)
      count += upper_bound(span(L,b+1,N), max_c) - lower_bound(span(L,b+1,N), min_c);
    }
  }
  cout << count << endl;
}

int main() {
  input();
  solve();
  return 0;
}