square869120Contest #6 B AtCoder Market

公式解説だと中央値を取っているが、そこまで気づかなくても単調性にさえ気づけば三分探索でゴリ押せる。整数の三分探索は実装が大変なので、実数で三分探索してあとで丸める。

constexpr double count(double pos, const vector<ll>& a, int n) {
  double ret = 0;
  rep(i, n) {
    ret += abs(pos-a[i]);
  }
  return ret;
}

constexpr double ternary_search(const vector<ll>& a, int n) {
  constexpr double eps = 1e-2;
  double mi = 0;
  double ma = 1e+9;
  while(mi+eps<ma) {
    auto med1 = (mi+ma+mi)/3.0;
    auto med2 = (mi+ma+ma)/3.0;
    auto cnt1 = count(med1, a, n);
    auto cnt2 = count(med2, a, n);
    if (cnt1 < cnt2) {
      ma = med2;
    } else {
      mi = med1;
    }
  }
  return round(mi);
}

int main() {
  int n; cin >> n;
  vector<ll> a(n), b(n);
  rep(i, n) {
    cin >> a[i] >> b[i];
  }

  ll suma = 0;
  ll sumb = 0;
  ll ans = 0;
  rep(i, n) {
    suma += a[i];
    sumb += b[i];
    ans += b[i] - a[i];
  }

  double a0 = ternary_search(a, n);
  double b0 = ternary_search(b, n);

  rep(i, n) {
    ans += abs(a[i]-a0);
    ans += abs(b[i]-b0);
  }
  cout << ans << endl;
}

リファクタ前の提出コード: Submission #4992747 - square869120Contest #6

• ここでは三分探索の結果を切り上げたものと切り捨てたものを両方試しているが、四捨五入するだけで十分だと後から気づいた