【C#】三角形が成立する条件の言い換え AtCoder Beginner Contest 143 D問題
蟻本を読んでいたら、三角形の条件の言い変えが乗っていたので、ちょっとメモとして残します。
三角形が成立する条件
問題にもあるように、三角形が存在する必要十分条件は辺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(n3)での計算なるのですが、二分探索を使うとO(nlongn)で計算することができます。つまり、a,bを固定して、c<a+bを満たすcを調べるときに二分探索を使用しますAtCoderの場合、後者で計算しないと間に合わないです。
実装
実装を載せておきます github.com