【C#】三角形が成立する条件の言い換え AtCoder Beginner Contest 143 D問題

蟻本を読んでいたら、三角形の条件の言い変えが乗っていたので、ちょっとメモとして残します。

atcoder.jp

三角形が成立する条件

問題にもあるように、三角形が存在する必要十分条件は辺a,b,cが下記の条件を満たすことです。

1.a<b+c
2.b<c+a
3.c<a+b

これを言い換えると、最も長い辺の長さ<他の2辺の長さの和となります。たとえば、a<b<cという条件だった場合、最大辺が右辺にあるものは明らかであるため、実際には3がわかれば良いと言えます。

ABC143Dの解法

ABC143において、与えられた辺の長さの配列を昇順にソートしたうえで、c<a+bの関係が崩れないように辺を選択していけば良いです。愚直に解くとO(n³)での計算なるのですが、二分探索を使うとO(nlongn)で計算することができます。つまり、a,bを固定して、c<a+bを満たすcを調べるときに二分探索を使用しますAtCoderの場合、後者で計算しないと間に合わないです。

実装

実装を載せておきます github.com