AtCoder abc255 参加メモ

Aising Programming Contest 2022（AtCoder Beginner Contest 255） - AtCoder

B - Light It Up

Bにしては難しい

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

int main() {
  int n,k; cin >> n >> k;
  vector<int> a(k),x(n),y(n);
  REP(i,k) { cin >> a[i]; a[i]--; }
  REP(i,n) cin >> x[i] >> y[i];

  double ans = 0;
  REP(i,n) {
    double now = 1e6;
    for(int j: a) {
      double dx = x[i]-x[j];
      double dy = y[i]-y[j];
      now = min(now, sqrt(dx*dx + dy*dy));
    }
    ans = max(ans,now);
  }

  printf("%0.10f\n", ans);
  return 0;
}

C - ±1 Operation 1

Xが初項から末項の間かどうかで場合分けして考える。

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
using ll = long long;

int main() {
  ll x,a,d,n; cin >> x >> a >> d >> n;

  x -= a;
  ll left, right;
  if (0 < d) {
    left = 0;
    right = d*(n-1);
  } else {
    left = d*(n-1);
    right = 0;
  }

  ll ans = min(abs(x-left), abs(x-right));
  if (d != 0 && left <= x && x <= right) {
    ll m = abs(x) % abs(d);
    ans = min(ans, m);
    ans = min(ans, abs(d) - m);
  }

  cout << ans << endl;
  return 0;
}

二分探索による別解

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
using ll = long long;

int main() {
  ll x,a,d,n; cin >> x >> a >> d >> n;

  if (d < 0) {
    a = a + d * (n-1);
    d = -d;
  }

  ll l = 0, r = n-1;
  while(abs(r-l) > 1) {
    ll mid = (r+l)/2;
    if (a + d * (mid) < x) l = mid;
    else r = mid;
  }

  ll ans = abs(x - (a + d * l));
  if (l < n-1) ans = min(ans, abs(x - (a + d * (l+1) )));

  cout << ans << endl;
  return 0;
}

D - ±1 Operation 2

• Aをソートする
• Xより大きくなるAのindexを二分探索で求める
• Aの累積和を取っておくと、X以下の合計とXより大きい部分の合計をO(1)で求められるので、それぞれの差分を合算することで必要な最小の操作回数を求められる

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
using ll = long long;

int main() {
  int n,q; cin >> n >> q;
  vector<int> a(n);
  REP(i,n) cin >> a[i];

  sort(a.begin(), a.end());
  vector<ll> m(n+1); // 累積和
  REP(i,n) m[i+1] = m[i]+a[i];

  REP(i,q) {
    ll x; cin >> x;
    auto it = upper_bound(a.begin(), a.end(), x);
    int idx = it - a.begin(); // xより大きい最も左側のindex

    ll d1 = m[idx] - m[0]; // x以下の部分の累積和
    ll ans = x * idx - d1;
    ll d2 = m[n] - m[idx]; // xより大きい部分の累積和
    ans += d2 - x * (n - idx);

    cout << ans << endl;
  }
  return 0;
}