Triangles [AtCoder Beginner Contest 143 D]

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

前提知識

• 累積和

解説

https://atcoder.jp/contests/abc143/submissions/8038987

まずは全探索を考える。
a,b,cを全探索して、条件を満たすか考える。
これは組み合わせが10⁹くらいなのでダメ。
でも、a,b全探索なら10⁶くらいなので、まだ余地がありそう。

a,bが固定してあると、cは以下の条件を満たす必要がある。

a - b < c
b - a < c
c < a + b

上2つはまとめられる

max(a-b, b-a) < c < a+b

これを満たすcを数えればいい。
Lは[1,10³]なので、
cnt[len] := 長さがlenである棒の個数
を作り、累積和を使うことで、条件を満たすcの組み合わせは高速に求めることができる。
注意として、a,bで選択した棒がcに入る場合があるので、その場合は抜かす。
最後に使われている棒は同じで順番だけ違うものも重複して数えているので、3!で割ると答え。

int N, L[2010], cnt[2010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> L[i];

    rep(i, 0, N) cnt[L[i]]++;
    rep(i, 1, 2010) cnt[i] += cnt[i - 1];

    ll ans = 0;
    rep(a, 0, N) rep(b, 0, N) if (a != b) {
        int mi = max(L[a] - L[b], L[b] - L[a]);
        int ma = L[a] + L[b];

        int cn = 0;
        if (0 <= ma - 1) cn = cnt[ma - 1];
        cn -= cnt[mi];

        if (mi < L[a] and L[a] < ma) cn--;
        if (mi < L[b] and L[b] < ma) cn--;

        ans += cn;
    }
    ans /= 6;
    cout << ans << endl;
}