https://beta.atcoder.jp/contests/bitflyer2018-qual/tasks/bitflyer2018_qual_c
考察
1. まずはどこかを全探索する
2. とりあえずiの位置を全探索してみるが、jの位置によってkの範囲が変わるので無理そう
3. jの位置を全探索してみると、iとkを取る範囲は特定できるが、iとkの距離をうまく扱えない感じがある
4. ===ここで一旦Dを通して帰ってくる===
5. jの位置を全探索すると、条件を満たさない組なら高速に求めることができそう
6. 条件を満たさない組の個数を求めることにしよう
7. これならできる
前提知識
解説
https://beta.atcoder.jp/contests/bitflyer2018-qual/submissions/2599738
条件を満たすものの個数を(全組み合わせ)-(条件を満たさない組み合わせ)で求める方針でやろう。
まずは事前に配列A,Bをしゃくとり法を使って事前計算しておこう。
A[i] := X[i]より左側で差がD以下の要素が何個あるか
B[i] := X[i]より右側で差がD以下の要素が何個あるか
条件を満たさない組み合わせは以下の4つがある
1. X[i]とX[k]の差がD以下
2. X[i]とX[k]の差がDより大きいが、X[i]とX[j]の差だけがDより大きい
3. X[i]とX[k]の差がDより大きいが、X[j]とX[k]の差だけがDより大きい
4. X[i]とX[k]の差がDより大きいが、X[i]とX[j]の差とX[j]とX[k]の差の両方がDより大きい
1はkを全探索する。
すると、iとjはA[k]から2つ選ぶ必要があるので、C(A[k],2)=A[k]*(A[k]-1)/2
2以降はjを全探索する。
jを固定すると、iの候補がA[j]個、kの候補がB[j]個となる。
iになれるが差がDより大きい個数をn, kになれるが差がDより大きい個数をmとすると、
2はn*B[j]
3はA[j]*m
4はn*m
となり、これを引いていく。
全組み合わせはC(N,3)=N*(N-1)*(N-2)/6なので、ここから4つを引いたら答え。
ll N, D, X[101010]; ll A[101010], B[101010]; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N >> D; rep(i, 0, N) cin >> X[i]; ll ans = N * (N - 1) * (N - 2) / 6; int L = 0; rep(R, 0, N) { while (L < R and D < X[R] - X[L]) L++; A[R] = R - L; } int R = N - 1; rrep(L, N - 1, 0) { while (L < R and D < X[R] - X[L]) R--; B[L] = R - L; } rep(i, 0, N) { ans -= A[i] * (A[i] - 1) / 2; // 1 ll n = i - A[i]; ll m = N - (i + 1) - B[i]; ans -= n * m; // 4 ans -= n * B[i]; // 2 ans -= A[i] * m; // 3 } cout << ans << endl; }