【AtCoder】尺取り法

ポイント

• 2つの変数を用意して、一方の変数を追いかけるようにもう一方の変数を動かしていく
• 単調性を利用するので、配列要素の順番を動かしていく場合には配列を予めソートしておく

例題

ABC212C - Min Difference

#include <bits/stdc++.h>
using namespace std;
#define all(a) (a).begin(), (a).end()
#define rep(i, n) for (int i = 0; i < (n); ++i)

const int INF = 1001001001;
void chmin(int &a, int b) { if (a > b) a = b; }

int main() {
  int N, M; cin >> N >> M;
  vector<int> A(N), B(M);
  rep(i, N) cin >> A[i];
  rep(i, M) cin >> B[i];
  
  sort(all(A));
  sort(all(B));
  
  int j = 0, ans = INF;
  rep(i, N) {
    // 末端まで行くか「B[j] >= A[i]」を満たすようになるまでjを増やしていく
    while (j + 1 < M && B[j] < A[i]) j++;
    chmin(ans, abs(A[i] - B[j]));
    if (j - 1 >= 0) chmin(ans, abs(A[i] - B[j - 1]));
  }
  
  cout << ans << endl;
}

ABC330C - Minimize Abs 2

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int INF = 1001001001;
void chmin(ll &a, ll b) { if (a > b) a = b; }

int main() {
  ll D; cin >> D;
  
  ll y = 2e6, ans = D;
  for (ll x = 0; x * x <= D; x++) {
    while (y > 0 && x*x + y*y >= D) y--;
    ll v1 = abs(x*x + y*y - D);
    ll v2 = abs(x*x + (y+1)*(y+1) - D);
    chmin(ans, v1); chmin(ans, v2);
  }
  
  cout << ans << endl;
}