[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;
}