SRM 506 Div1 easy SlimeXSlimesCity

topcoder

問題概要

最大50個の街がある。
それぞれの人口が与えられる。
これらの街を一つに統合していく。
ある二つの街を統合するとき、人口の多い方の街の名前になる。
一つの街にしたとき、何種類の名前があり得るでしょうか。

解法

貪欲
すべての街について、統合後がその街の名前になるか検証していく。
一番大きな街は、すべての街を自分にどんどん統合していけばその名前になる。
それ以外の街は、自分より小さな街を自分にどんどん統合していく。
そうすると、自分以下の大きさの街の合計の人口でその街の名前の街ができる。
今度は残った街を小さい順に統合していく。

  • 全て統合できれば、その街は最後の街の名前になれる。
  • 統合できなければ、どうやってもその街の名前でそれ以上人口を大きくできないので、最後の名前になることできない。（自分の人口以下の街しか統合できないことから）。
  • 統合する順番が変わっても、統合した街が同じなら人口は変わらないことから、まず最初に自分より小さな街を先に統合してもよい。自分の初期の人口より小さい街はどんな順番で統合しても必ず統合できる。

自分より大きな街は

  • その中で任意のものを統合して、その街より小さな街を統合できなくなることはない。
  • その中で任意のものを統合して、その街より大きな街を統合できるようになることはある。

そのことから、小さい順に試していけば正しい。
ちなみに、
一つ大きな街が自分より小さな街を全て統合したときと、
今の街に一つの大きな街を統合した場合と人口が等しくなる。
よって、全部ためさなくても一つ大きな街がその候補で自分と統合できるとき、
その街は最後の街の名前になれる。

ソース

#include<iostream>
#include<algorithm>
#include<vector>

#define REP(i,b,n) for(int i=b;i<(int)n;i++)
#define rep(i,n)   REP(i,0,n)
#define ALL(C)     (C).begin(),(C).end()

using namespace std;
typedef long long lli;

class SlimeXSlimesCity {
public:
  int merge(vector <int> p) {
    sort(ALL(p));
    lli sum[50];
    rep(i, 50)sum[i] = 0;
    int n = p.size();
    sum[0] = p[0];
    REP(i,1, n){
      sum[i] = (lli)p[i] + sum[i-1];
    }
    bool res[50];
    rep(i, 50)res[i] = false;
    res[n-1] = true;
    for(int i = n-2;i>=0;i--){
      if(res[i+1] && sum[i] >= (lli)p[i+1])res[i] = true;
    }
    int cnt = 0;
    rep(i, n){
      if(res[i])cnt++;
    }
    return cnt;
  }
};