IOI 2009 Bulgaria過去問 Hiring - TopCoderとJ言語と時々F#

解法

まず各労働者iについて、値 S_i / Q_iを考える。これについて以下のことがわかる。

 S_a / Q_a < S_b / Q_b のとき、労働者bを給料S_bで雇うと労働者aは給料(Q_a / Q_b) * S_b で雇える

労働者bを給料S_bで雇ったとき、法律の規定で労働者aには(Q_a / Q_b) * S_b以上の給料を払わねばならないが、一方で労働者aは最低賃金として給料S_aを要求している。すなわち労働者aを雇うのに必要な給料は max(S_a, (Q_a / Q_b) * S_b) である。

このときS_a / Q_a < S_b / Q_bを変形すると S_a < (Q_a / Q_b) * S_b となるから、労働者aを雇うのには(Q_a / Q_b) * S_bだけの給料で十分である。

次に、雇う労働者たちのうち最も S / Q の値が大きい労働者を m とする。すると他の労働者kを雇うのには Q_k / Q_m * S_m だけの給料が必要になる。これはすなわち、最も S / Q の値が大きい労働者を固定すれば、その他の労働者を雇うのに必要な給料の額は Q のみの式(Qの一次関数)で表せるということである。

S / Qの最も大きい労働者mを固定したときに、他の労働者をどう選べばよりたくさんの労働者が雇えるかを考える。ある労働者を雇うのに必要な給料の額は Q に関して単調増加なので、(選んだ労働者のQの合計) / Q_m * S_m が超えない範囲でQの低い労働者たちを選んでいけばよい。これをそのまま実装すると、各労働者について、その労働者をS / Qが最大であると固定して調べなければならないので O(N²) となり N <= 5000 のケースについては間に合う。

N <= 500000のケースに対応するにはより効率のよいアルゴリズムが必要になる。ここで、労働者をヒープで管理することを考える。ヒープの比較に使われるキーはQの値である。労働者iをS / Qが最大の労働者と仮定するとき、まずヒープにQ_iを挿入する。そして、(ヒープに入っているQの値の合計値) / Q_i * S_i がWを超えている間、ヒープから最大のQを削除していく。(ヒープに入っているQの値の合計値) / Q_i * S_iがW以下になった時点でヒープに格納されている要素数が、労働者iを最大のS / Qを持つ労働者と仮定したときに雇える最大の人数となる。このアルゴリズムでは、各労働者は1回だけヒープに挿入され、最高で1回ヒープから削除されるから、実行時間は O(N lg N) となり N <= 500000 のケースでも間に合う。

ソース

/*
  TASK: Hiring (IOI 2009 Bulgaria)
  LANG: C++
  NAME: JAPLJ

  Problem URL: http://ioi-jp.org/ioi/2009/problems/day1/Hiring_jp.pdf
 */

#include<cstdio>
#include<queue>
#include<algorithm>

using namespace std;

typedef long long ll;

struct cand {
  int S, Q, idx;
};

bool operator < (const cand& a, const cand& b)
{
  return (double)a.S / a.Q < (double)b.S / b.Q;
}

cand C[500000];
bool hire[500000];

int main()
{
  int N;
  ll W;
  scanf("%d%lld", &N, &W);
  for(int i=0; i<N; ++i) {
    C[i].idx = i;
    scanf("%d%d", &C[i].S, &C[i].Q);
  }
  sort(C, C+N);
  priority_queue<int> QQ;
  int sol = 0, bestIdx;
  double bestCost;
  ll totalQ = 0LL;
  for(int i=0; i<N; ++i) {
    QQ.push(C[i].Q);
    totalQ += C[i].Q;
    double maxQ = (double)W * C[i].Q / C[i].S;
    while(totalQ > maxQ) {
      totalQ -= QQ.top();
      QQ.pop();
    }
    double totalCost = (double)totalQ / C[i].Q * C[i].S;
    if(sol < QQ.size() || (sol == QQ.size() && bestCost > totalCost)) {
      sol = QQ.size();
      bestCost = totalCost;
      bestIdx = i;
    }
  }
  priority_queue<pair<int, int> > QCand;
  for(int i=0; i<=bestIdx; ++i) {
    QCand.push(make_pair(C[i].Q, C[i].idx));
    hire[C[i].idx] = true;
  }
  while(sol < QCand.size()) {
    hire[QCand.top().second] = false;
    QCand.pop();
  }
  printf("%d\n", sol);
  for(int i=0; i<N; ++i)
    if(hire[i])
      printf("%d\n", i+1);
  return 0;
}