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; } };