codeFlyer （bitFlyer Programming Contest）予選 C - 徒歩圏内

問題
提出コード
これを自力で解けなかったのは結構悔しいです…最近思い通りになかなか解けないですね

解法

,,となるようなの組を探します。
要素が3つ存在するので、まずは真ん中を決め打ちしたときののペアの個数を求めることを考えます。
あるについて、となるようなおよびとなるようなの個数は、それぞれ二分探索で求めることができます。

• の個数
  を満たすことから、式変形をするとを満たす必要があります。ということで、までで、上の条件をみたすものの個数を調べるため、
  から、となるの個数を引けばよいです。
  これは、二分探索を利用することで求められます。

• の個数
  を満たすことから、を満たす必要があります。
  ということで、以降でこの条件を満たす区間の個数を求めるため、
  となるの個数から、を引けばよいです。

ということで、との個数を求められたので、のペアの個数は、それぞれの個数の積になります。
ただし、このままだとを満たさないものが存在しています。
ということで、最後にこうならないものを全体から引けば、答えが求まります。

• となるの組の個数を求める
  となるのペアを決めたとき、ありうるは～です。
  今回は、を決め打ったときに、上のをみたすのペアの個数を求めていきます。
  となるの中で、最も遠いようなをまず探します。
  これは、二分探索で求めることができます。これを仮にとします。
  すると、のペアは、今求めた～今求めたの中から2つの数字を選ぶ方法と同じになります。
  このとき、すべてのについてを満たしています。なぜなら、がこの条件を満たすの中で最も遠い場所になるので、それより後ろの場所をとしても、との距離は小さくなるだけです。
  ということで、から、となるの個数をとしたときに、
  となるの組の個数は、
  
  となります。
  全てのについてこれを求め、最初に数えたものから引いていけば、最終的な答えとなります。