SRM 506 DIV1 Easy SlimeXSlimesCity

http://apps.topcoder.com/stat?c=problem_statement&pm=11154&rd=14435

問題

都市がいくつか(N<=50)あって0〜N-1と名前がつけられていて、それぞれには人口がある(p[i]<=10^9)
都市が1つになるまで、それらの任意の2つを選び合併、
新しい都市の人口は2つの都市の和で、新しい都市の名前は元の人口が多かった方、ただし同数の場合はどちらかを任意に選べる。
を繰り返すとき、最後に残りうる都市の名前の種類の数を求めろ

回答

逆に考える。
ある都市が生き残れるかどうかを判断する。このためには、単にできるかぎり都市の名前がのこるように合併し続け、1つになれたら大丈夫。
オーバーフローに注意、だがサンプルにオーバーフローしうるケースがあったのでFailedは少なかったようだ

コメント

時間かかってしまった。
逆に考えることは基本的

コード

一部冗長なところがある

#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#define aut(v, x) __typeof(x) v = (x)
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
using namespace std;
typedef long long ll; typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pii> vpii;
const int INF = 0x3f3f3f3f; const ll INFL = 0x3f3f3f3f3f3f3f3fLL;

struct SlimeXSlimesCity {
	int merge(vector <int> p_) {
		int n = p_.size();
		vector<ll> p; rep(i, n) p.pb(p_[i]);
		int r = 0;
		rep(i, n) {
			vector<int> b(n,0);
			ll x = p[i];
			b[i] = 1;
			while(1) {
				rep(j, n) if(!b[j] && x >= p[j]) {
					b[j] = 1; x += p[j];
					goto change;
				}
				break;
				change:;
			}
//ここは、単に、b[j]が埋まっていることを確認、や、都市数をカウントすればいい
			ll y = 0;
			rep(j, n) if(!b[j]) y += p[j];
			if(y <= x) r ++;
			cout << i << ": " << x << ", " << y << endl;
		}
		return r;
	}
};