【競プロ】1日1AC : ABC143 D問題 Triangles

今日はすでに1記事書いていますが、せっかくなのでもう1問。

Diffは678（茶）です。

提出コードと考え方

蟻本などでこの問題を見たことがある人がいるかもしれませんが、制約が少し厳しくなっています。

制約的に \(\mathcal{O}(N^2)\) までなら大丈夫そうです。先に2本の辺を選んで固定し、残りの1本として考えられるものを高速に求めることができればいいでしょう。

問題文には三角形の成立条件が並んでいますが、選ぶ棒の長さを \(a,b,c\ (a\leq b\leq c)\) とすると \(c<a+b\) さえ成り立てばいいことが分かります。

ここでは \(a,b\) の長さの棒を先に決め、\(c\) の長さの棒として考えられるものの本数を考えます。なお、\(L_i\) はソート済みとします。

最後の \(1\) 本として選べるのは、

\[N-(2\ \mbox{本目よりインデックスが小さい棒の本数})-(c\ge a+b\ \mbox{を満たす棒の本数})\]

本だけあります。

この「\(c\ge a+b\) を満たす棒の本数」はSTLの関数を用いて処理できます。

Lはソートされたvectorの配列であるとして、

lower_bound(L.begin(),L.end(),v)

は、配列Lの全要素の中で値が \(v\) 以上となる最小の要素のイテレータを返します。（最初の \(2\) つの引数は \(L\) のうち、調べる範囲をイテレータで指定します。ここでは全要素を指定。）

存在しない場合はL.end()が返ってきます。

auto itr = lower_bound(L.begin(),L.end(),v);

とすれば、変数に保存できます。

次に、値が一定以上である要素数を数えます。

distance(itr,L.end())

とすると、この値が得られます。イテレータL.end()は最終要素の次を指すイテレータです。distance関数でitrとの距離を求めているわけです。

では実装です。以下のようにコードが書けるでしょう。

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i < (n);i++)
using namespace std;

int main(){
    int n;
    cin >> n;
    vector<int> l(n);
    rep(i,n) cin >> l[i];
    sort(l.begin(),l.end());
    int ans = 0;
    for(int i = 0;i < n;i++){
        for(int j = i+1;j < n;j++){
            auto itr = lower_bound(l.begin(),l.end(),l[i]+l[j]);
            int d = distance(itr,l.end());
            ans += n-(j+1)-d;
        }
    }
    cout << ans << endl;
    return 0;
}