AtCoder Beginer Contest 143 - D
- AtCoder Beginer Contest 143 - D Triangles
- N本の棒が与えられる、それを３本ずつ使ったとき三角形が作れる組み合わせをすべて数え上げる
- 条件：３本の棒をa,b,cとしたときa<b+c, b<c+a, c<a+b
解説
二分探索を使う
- 最初に使う２本の棒を決める(仮にa,bとする）
- 最後の棒を二分探索で求める
- 二分探索の条件が難しい
二分探索の詳細
- 二分探索のためN本の棒の長さをソートしておく
- 一番長い棒をa(mid), 次に長い棒をb(low)と決める
- 上記をfor文による二重ループで表現する（逆順でたどる）
- N本の棒のうちbより小さいものが探索の対象となる
- そして、二分探索の条件は(a-b<c)&&(b-a<c)なんだけど、a>bなのでa-b<cでよい
- 二分探索で出てきたインデックスをいい感じにカウントすれば答えが出る
これを実装すれば解答の通り、計算量はO(N*N*logN)になる。一応Rubyでも2秒以内に間に合った。