n 個の整数 a₁ … aₙ と整数 k が与えられる。
二つの位置 i < j のうち |aᵢ − aⱼ| ≤ k となるものが何組あるかを出力せよ。
値が同じでも位置が違えば別の数とみなす。
同じ二つの位置の順番を入れ替えただけのもの（i, j と j, i）は一組である。
n = 1 なら答えは 0 である。
一行目に n と k、二行目に a₁ … aₙ が空白区切りで与えられる。
5 3 1 9 4 7 3
5
2 1000000000 -2000000000 2000000000
0
実行すると、これらの行が順に input()・標準入力に渡されます(実行中に入力を求めません)。
$ 準備完了
コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。
すべての二つ組を試すと n²/2 = 5 千万回なので、Craykon は実行ステップ上限（約 5 千万）を超え、Python も遅くなります。
並べ替えると、a[j] との差が k 以下の数は a[j] のすぐ前の一区間 a[i..j−1] になり、j が右へ進むほど i も右へしか進みません（二つのポインタ）。
並べ替え n log n と走査 2n で終わります。
並べ替えは言語ごとに違います。
Python sorted()、Java Arrays.sort()、C# Array.Sort()、C++ std::sort は数を大きさの順に並べます。
Craykon の a.並べ替え() も基準関数を省くと数は小さい順です。
ところが JavaScript・TypeScript の sort() は比較関数を渡さないと文字列に変えて辞書順に並べるので、10 が 9 より、-1 が -2 より前に来ます — a.sort((x, y) => x - y) のように関数を渡します。
C の qsort も比較関数を関数ポインタで受け取りますが、よく使う return x - y; は 2×10⁹ − (−2×10⁹) で int があふれて順番が逆になります — (x > y) - (x < y) で大小だけを比べます。
同じあふれが二つのポインタの a[j] - a[i] にもあります：差は 4×10⁹ までなので Java・C#・C・C++ は long/long long に変えて引く必要があり、そうしないと例 2 が 1 になります。
そして「以下」なので差が > k のときだけ i を動かします — >= k で動かすと k = 0 のとき同じ値どうしの組を落とします。
n, k = map(int, input().split())a = sorted(map(int, input().split())) # 정렬하면 a[j]와 차이가 k 이하인 것은 a[j] 바로 앞의 한 구간이다.# j가 오른쪽으로 갈수록 구간의 왼쪽 끝 i도 오른쪽으로만 간다(두 포인터).count = 0i = 0for j in range(n): while a[j] - a[i] > k: i += 1 count += j - i # a[i..j-1]이 모두 짝이 된다print(count)const [n, k, ...a] = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);// sort()에 비교 함수를 넘기지 않으면 문자열로 바꿔 사전 순으로 늘어놓는다(10이 9보다 앞)a.sort((x, y) => x - y); // a[j]와 차이가 k 이하인 것은 a[j] 바로 앞의 한 구간이다. 왼쪽 끝 i는 오른쪽으로만 간다.let count = 0;let i = 0;for (let j = 0; j < n; j++) { while (a[j] - a[i] > k) i++; count += j - i;}console.log(count);import { readFileSync } from "node:fs"; const [n, k, ...a]: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);// sort()에 비교 함수를 넘기지 않으면 문자열로 바꿔 사전 순으로 늘어놓는다(10이 9보다 앞)a.sort((x: number, y: number): number => x - y); // a[j]와 차이가 k 이하인 것은 a[j] 바로 앞의 한 구간이다. 왼쪽 끝 i는 오른쪽으로만 간다.let count = 0;let i = 0;for (let j = 0; j < n; j++) { while (a[j] - a[i] > k) i++; count += j - i;}console.log(count);import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(in.readLine()); int n = Integer.parseInt(st.nextToken()); int k = Integer.parseInt(st.nextToken()); int[] a = new int[n]; st = new StringTokenizer(in.readLine()); for (int i = 0; i < n; i++) a[i] = Integer.parseInt(st.nextToken()); Arrays.sort(a); // a[j]와 차이가 k 이하인 것은 a[j] 바로 앞의 한 구간이다. 왼쪽 끝 i는 오른쪽으로만 간다. long count = 0; int i = 0; for (int j = 0; j < n; j++) { while ((long) a[j] - a[i] > k) i++; // 차이는 4×10⁹까지라 long으로 뺀다 count += j - i; } System.out.println(count); }}using System;using System.Linq; class Program{ static void Main() { string[] first = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(first[0]); long k = long.Parse(first[1]); long[] a = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(long.Parse).ToArray(); Array.Sort(a); // a[j]와 차이가 k 이하인 것은 a[j] 바로 앞의 한 구간이다. 왼쪽 끝 i는 오른쪽으로만 간다. long count = 0; int i = 0; for (int j = 0; j < n; j++) { while (a[j] - a[i] > k) i++; // long이라 4×10⁹ 차이도 넘치지 않는다 count += j - i; } Console.WriteLine(count); }}#include <algorithm>#include <iostream>#include <vector> int main() { int n; long long k; std::cin >> n >> k; std::vector<long long> a(n); for (long long& x : a) std::cin >> x; std::sort(a.begin(), a.end()); // a[j]와 차이가 k 이하인 것은 a[j] 바로 앞의 한 구간이다. 왼쪽 끝 i는 오른쪽으로만 간다. long long count = 0; int i = 0; for (int j = 0; j < n; j++) { while (a[j] - a[i] > k) i++; count += j - i; } std::cout << count << "\n";}#include <stdio.h>#include <stdlib.h> static int a[10000]; /* qsort에 넘기는 비교 함수. x - y로 돌려주면 int를 넘칠 수 있어서 크기만 비교한다. */static int ascending(const void* p, const void* q) { int x = *(const int*)p, y = *(const int*)q; return (x > y) - (x < y);} int main(void) { int n, k; scanf("%d %d", &n, &k); for (int i = 0; i < n; i++) scanf("%d", &a[i]); qsort(a, n, sizeof a[0], ascending); /* a[j]와 차이가 k 이하인 것은 a[j] 바로 앞의 한 구간이다. 왼쪽 끝 i는 오른쪽으로만 간다. */ long long count = 0; int i = 0; for (int j = 0; j < n; j++) { while ((long long)a[j] - a[i] > k) i++; /* 차이는 4×10⁹까지 */ count += j - i; } printf("%lld\n", count); return 0;}첫줄 = コンソール.数読み();n = 첫줄[0];k = 첫줄[1];a = コンソール.数読み();// 기준 함수를 주지 않으면 수는 작은 것부터 늘어놓는다a.並べ替え(); // a[j]와 차이가 k 이하인 것은 a[j] 바로 앞의 한 구간이다. 왼쪽 끝 i는 오른쪽으로만 간다.count = 0;i = 0;繰り返す (j = 0; j < n; j++){ 間 (a[j] - a[i] > k) { i += 1; } count += j - i;}コンソール.書く(count);