[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 \) の個数は二分探索によって計算ができます。

コード