Codeforces Round #352 Div2 C, D

C. Recycling Bottles

Problem - C - Codeforces

問題

2次元平面で Adil が (ax, ay) に、Bera が (bx, by) にいる。ゴミ箱が (tx, ty) にあり、ゴミが散らばっている。2人は以下の操作を繰り返す。
落ちているゴミを選び、そこまで行く。
ゴミを拾い、ゴミ箱へ行く。
ゴミをゴミ箱へ入れる。
2人は独立に動くことができる。全てのゴミがゴミ箱に入るまでの2人の動いたユークリッド距離の和を最小化せよ。

解法

2人はそれぞれ1回ずつ (自分のいる場所)->(ゴミの場所)->(ゴミ箱)という経路で移動できるが、それ以外は(ゴミ箱)->(ゴミの場所)->(ゴミ箱)というように、ゴミ箱とゴミの往復になる。よって解は以下の3通りのいずれかになる。
Adil が最初にゴミiを拾いに行き、Beraが最初にゴミjを拾いに行く。
Adil が最初にゴミiを拾いに行き、Beraは動かない。
Adil は動かず、Beraが最初にゴミjを拾いに行く。
あとはこのiとjを選べばいい。

コード

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

template <class T, class U>
void chmin(T &t, U f) {
  if (t > f) t = f;
}


double dist(int x1, int y1, int x2, int y2) {
  double dx = abs(x1 - x2);
  double dy = abs(y1 - y2);
  return sqrt(dx * dx + dy * dy);
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int ax, ay, bx, by, tx, ty;
  cin >> ax >> ay >> bx >> by >> tx >> ty;
  int N;
  cin >> N;
  vector<int> x(N), y(N);
  for (int i = 0; i < N; ++i) cin >> x[i] >> y[i];
  double sum = 0.0;
  priority_queue<pair<double, int>> adil, bera;
  for (int i = 0; i < N; ++i) {
    double d = dist(tx, ty, x[i], y[i]);
    sum += d * 2.0;
    double da = dist(ax, ay, x[i], y[i]);
    adil.emplace(da - d, i);
    if (adil.size() == 3) adil.pop();
    double db = dist(bx, by, x[i], y[i]);
    bera.emplace(db - d, i);
    if (bera.size() == 3) bera.pop();
  }
  vector<pair<double, int>> adil_v, bera_v;
  while (!adil.empty()) adil_v.push_back(adil.top()), adil.pop();
  while (!bera.empty()) bera_v.push_back(bera.top()), bera.pop();
  double ans = 1e18;
  for (pair<double, int> a : adil_v)
    for (pair<double, int> b : bera_v) {
      chmin(ans, sum + a.first);
      chmin(ans, sum + b.first);
      if (a.second == b.second) continue;
      chmin(ans, sum + a.first + b.first);
    }
  printf("%.15f\n", ans);
}

D. Robin Hood

Problem - D - Codeforces

問題

N人の人がいて、それぞれciずつコインを持っている。以下の操作をK回繰り返す。
一番多くコインを持っている人（複数いる場合はランダムに1人選ぶ）からコインを1没収する。
コインの枚数が一番少ない人（複数いる場合はランダムに1人選ぶ）にコインを1与える。
K回の操作のあと、最も多くコインを持っている人と最も少ない人の差は何枚になるか。
解法
この操作は十分に多い回数繰り返されると全体が平均に近づいていく。L以下のコインの人を全員Lに引き上げたとしてもKを超えないような最大のLを選び、まずはL以下の人を全員Lに引き上げる。その分のコインを多く持っている人から巻き上げる。この操作を行ったあとのKはN以下のはずなので、愚直にシミュレーションして求める。

コード

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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int64_t N, K;
  cin >> N >> K;
  vector<int64_t> coins(N);
  int64_t sum = 0;
  for (int i = 0; i < N; ++i) {
    cin >> coins[i];
    sum += coins[i];
  }
  int64_t average = sum / N;
  int64_t high = average, low = 0;
  while (high - low > 1) {
    int64_t mid = (high + low) / 2;
    int64_t need = 0;
    for (int i = 0; i < N; ++i)
      if (coins[i] < mid) need += (mid - coins[i]);
    if (need > K)
      high = mid;
    else
      low = mid;
  }
 
  // 貧乏人を全員lowまで引き上げる。
  int64_t cost = 0;
  for (int i = 0; i < N; ++i)
    if (coins[i] < low) {
      cost += (low - coins[i]);
      coins[i] = low;
    }
  K -= cost;
  map<int64_t, int> citizens;
  for (int i = 0; i < N; ++i) citizens[coins[i]]++;


  // 貧乏人を全員lowまで引き上げるのに必要なコインを金持ちから巻き上げる。
  while (cost > 0) {
    auto it_back = citizens.end();
    it_back--;
    int64_t richest_coin = it_back->first;
    int64_t richest_num = it_back->second;
    it_back--;
    int64_t next_richest_coin = it_back->first;
    if ((richest_coin - next_richest_coin) * richest_num > cost) {
      int64_t width = cost / richest_num;
      if (width > 0) {
        citizens.erase(richest_coin);
        citizens[richest_coin - width] += richest_num;
        cost -= richest_num * width;
      }
      citizens[richest_coin - width] -= cost;
      citizens[richest_coin - width - 1] += cost;
      cost = 0;
    } else {
      citizens.erase(richest_coin);
      citizens[next_richest_coin] += richest_num;
      cost -= (richest_coin - next_richest_coin) * richest_num;
    }
  }

  // 残りは愚直にシミュレーション
  while (K > 0) {
    auto richest = citizens.end();
    richest--;
    auto poorest = citizens.begin();
    if (richest->first - poorest->first <= 1) {
      cout << (richest->first - poorest->first) << endl;
      return 0;
    }
    int64_t mi = K;
    chmin(mi, richest->second);
    chmin(mi, poorest->second);
    int64_t richest_coin = richest->first;
    int64_t poorest_coin = poorest->first;
    citizens[richest_coin] -= mi;
    citizens[richest_coin - 1] += mi;
    citizens[poorest_coin] -= mi;
    citizens[poorest_coin + 1] += mi;
    if (citizens[richest_coin] == 0) citizens.erase(richest_coin);
    if (citizens[poorest_coin] == 0) citizens.erase(poorest_coin);
    K -= mi;
  }

  auto richest = citizens.end();
  richest--;
  auto poorest = citizens.begin();
  cout << (richest->first - poorest->first) << endl;
}