けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

2018 codeFlyer 予選 C 徒歩圏内 (400 点)

実装力って大事だなと。

Before: https://beta.atcoder.jp/contests/bitflyer2018-qual/submissions/2601840
After: https://beta.atcoder.jp/contests/bitflyer2018-qual/submissions/2603569

2018 codeFlyer 予選 C 徒歩圏内

問題概要

長さ  N の単調増加数列  X_1, X_2, ..., X_N が与えられる。添字  (i, j, k) の組で

  •  1 \le i <  j <  k \le N
  •  x_j - x_i \le D
  •  x_k - x_j \le D
  •  x_k - x_i >  D

を満たすものを数え上げよ。

制約

  • 3 <= N <= 105

解法

  1. X[j] - X[i] <= D かつ X[k] - X[j] <= D を満たす場合の数
  2. X[k] - X[i] <= D を満たす場合の数

をそれぞれ求めて、1 から 2 を引けば良い。
これらを求めるために、しゃくとり法によって以下を求めておく

  • L[i] := (X[i] - X[left] <= D となるような最小の left)
  • R[i] := (X[right] - X[i] <= D となるような最大の right)

1 は、j を固定して求める。
(R[j] - j) * (j - L[j]) を各 j に対して総和をとる

2 は、i を固定して求める (これを j を固定してやろうとして実装が煩雑になってしまった!!!!!!!!!!!!!)
R[i] - i 個から 2 個選ぶ問題になる。(R[i] - i) * (R[i] - i - 1) / 2 を各 i に対して総和をとる

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N, D;
    cin >> N >> D;
    vector<long long> X(N);
    for (int i = 0; i < N; ++i) cin >> X[i];
    
    vector<long long> L(N), R(N);
    int left = 0, right = 0;
    for (int mid = 0; mid < N; ++mid) {
        while (right < N && X[right] - X[mid] <= D) ++right;
        while (left < mid && X[mid] - X[left] > D) ++left;
        R[mid] = right - 1;
        L[mid] = left;
    }
    
    long long res = 0;
    for (long long mid = 0; mid < N; ++mid) res += (R[mid] - mid)  * (mid - L[mid]);
    for (long long left = 0; left < N; ++left) res -= (R[left] - left) * (R[left] - left - 1) / 2;
    cout << res << endl;
}