Make a Team [CPSCO2019 Session4 C]

https://atcoder.jp/contests/cpsco2019-s4/tasks/cpsco2019_s4_c

前提知識

• しゃくとり法

解説

https://atcoder.jp/contests/cpsco2019-s4/submissions/5285187

まず入力がソート可能なので、とりあえずしておこう。
どこから考えていこうかという感じだが、全探索対象を探す。
入力を見ると、N≦10^5なので、1つの要素しか全探索ができない。
ある要素R[i]について重複なく数えようと考えると、

• R[i]を必ず使う
• 他2つはiより添字が大きいものを使う

ことで重複なく漏れなく数えることができそうな感じがする。
他2つをどのように決めるかであるが、配列Rがソート済みなので、
R[i]+D以下の要素であればどれでも大丈夫そう。
これでうまく解けそうだ。
　
具体的な解法。R[i]を全探索する。
R[i]+D以下であり、R[i]以降の要素数otherをしゃくとり法を使って計算する。
otherが特定できたら、他2つを決めるので、C(other, 2)通りあり、これを答えに足していく。
二項係数の計算は真面目にやらなくても、C(other, 2)=other*(other+1)/2なので、これで計算すればいい。

int N, D, R[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N >> D;
	rep(i, 0, N) cin >> R[i];
	sort(R, R + N);
 
	ll ans = 0;
	int r = 0;
	rep(l, 0, N) {
		while (r < N and R[r] - R[l] <= D) r++;
		
		int other = r - l - 1;
		ans += 1LL * (other) * (other - 1) / 2;
	}
	cout << ans << endl;
}