[AtCoder] ABC 143 D – Triangles
問題
方針
全てのパターンについて調べると計算量が \( O(N^3) \) となるので間に合いません。なので、\( 2 \) 本を固定して考えます。
二分探索
\( a \leq b \leq c \) として、\( b, c\) を固定して探索を行います。\( b, c\) を固定して探索を行うために、\( L \) を昇順に並び替えて \( 2 \) 重ループで探索を行います。三角形の成立条件より、
\[c – b < a \leq b\]
を満たす \( a \) の個数を数え上げます。\( c – b < a \) を満たす \( a \) の個数は二分探索によって計算ができます。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { int N; cin >> N; vector<int> L(N); for (int i = 0; i < N; i++) { cin >> L[i]; } sort(L.begin(), L.end()); ll ans = 0; for (int i = 0; i < N; i++) { for (int j = i + 1; j < N; j++) { auto iter = lower_bound(L.begin(), L.end(), L[j] - L[i] + 1); int k = iter - L.begin(); ans += max(0ll, (ll)i - k); } } cout << ans << "\n"; return 0; }
ディスカッション
コメント一覧
まだ、コメントがありません