ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

TopCoder SRM 634 Div1 Easy : ShoppingSurveyDiv1

概要


N人がM種類の商品の中から買い物をする。
・何種類でも買ってもいいし、買わなくてもよい。
・ただし各商品はお一人様1つまでとなっていて同じ商品を複数買うことはできない。
・K種類以上の商品を買った人はbig shopperと呼ばれる。

M種類の商品をそれぞれ何人が買ったかというリストsがあるので、これを元にbig shopperの人数の最小値を求めよ。

解法


最初の自分の解法(下のコメントで消しているやつ)では、
・二分探索でbig shopperの人数を決めて、
・priority_queueで誰が何個買ったかを管理し、
・big shopperと思われる人物には商品を買わせ、
・残った分は商品の買った数が少ない人に買わせる。
・二分探索で定めた人数と実際K種類以上買った人数を比較...
という感じでごにょごにょやっていた。

非常に怪しい。(システムテストは通る)

他の方のコードを見てみたら、どうやらこんなごちゃごちゃしたことはしなくてもよいことが分かる。

big shopperの数を小さい順で調べていく。そのときbig shopperには(K種類買うと言わず)全種類の商品を買うと仮定する。そして残った商品の数がbig shopperでない人達で買うことができるかどうか(買う種類がK種類未満かどうか)を調べればよい。

この解法なら非常に短く書けて良い。

ソースコード

class ShoppingSurveyDiv1 {
public:

  int minValue(int N, int K, vector <int> s) {
    rep(i, N) {
      int count = 0;
      rep(j, s.size()) count += max(0, s[j] - i);
      if(count <= (N - i) * (K - 1)) return i;
    }
    return N;

    // int lb = -1;
    // int ub = N + 2;

    // while(ub - lb > 1) {
    //   int mid = (lb + ub) / 2;

    //   priority_queue<int> pq[2];
    //   rep(i, N) pq[0].push(0);
      
    //   rep(i, s.size()) {
    //     int curr = i % 2;
    //     int next = (i + 1) % 2;
    //     int ss = s[i];
        
    //     rep(j, N) {
    //       int cnt = pq[curr].top();
    //       pq[curr].pop();
    //       if(j < min(ss, mid) || N - 1 - max(0, ss - mid) < j) cnt++;
    //       pq[next].push(cnt);
    //     }
    //   }
      
    //   int count = 0;
    //   rep(i, N) {
    //     int cnt = pq[s.size() % 2].top();
    //     pq[s.size() % 2].pop();
    //     if(cnt >= K) count++;
    //   }

    //   if(count <= mid) ub = mid;
    //   else if(count > mid) lb = mid;
    // }

    // return ub;
  }