SRM 506 Div 1

TopCoder

本番には参加しなかったのでpracticeで解いた。

Easy SlimeXSlimesCity

問題概要

都市がn個あり、それぞれの人口が与えられる。
以下の操作を都市がひとつになるまで繰り返す。

2つの都市iとjを併合し、新しい都市とする。新しい都市の名前は人口が多かったほうの名前になる。同じだった場合どちらでもよい。


このとき、最後に残りうる都市の名前は何通りありうるか。
n≦50を満たす。

方針

都市iが残せるかどうかを考える。
これは、人口がi以下の都市をどんどんiに併合していって、iが最後のひとつになれるか見ればよい。


各都市についてこれを繰り返せばよい。

ソースコード
	int merge(vector <int> pp) 
	{
		int n=pp.size(),ans=0;
		rep(i,n){
			vector<ll> v;
			rep(j,n)v.pb(pp[j]);
			
			swap(v[0],v[i]);
			while(v.size()>1){
				int j=1;
				for(;j<v.size();j++)if(v[j]<=v[0])break;
				if(j==v.size())break;
				v[0]+=v[j];
				v.erase(v.begin()+j);
			}
			if(v.size()==1)ans++;
		}
		return ans;
	}

Medium SlimeXGrandSlimeAuto

問題概要

都市がn個ある。
都市と都市の距離が与えられる。
m台の車がそれぞれ都市cars[i]に止まっている（重複あり）。
都市から都市への移動手段には2通りがあり、ひとつは歩きで、もうひとつは車である。

一つの車は一度降りると二度と乗れなくなってしまう。


このとき、l個の都市districts[i]をこの順に訪問したい。
これにかかる最短の移動時間を求めよ。


最初に居る都市は0番目の都市である。
また、n,m,l≦50を満たす。

方針

districts[i]の都市へ（districts[i-1]の都市から）移動するのに、
車0,1,2,...,m-1を使用する場合または車を使わない場合がある。

徒歩の場合と、それぞれの車を使った場合を比較して
どれだけ早くなるかという行列をM[j][i]とすると、
これは仕事0,1,...,j,...,m-1を人0,1,...,i,...,l-1に重複なく割り当てて
利益を最大化するような問題であることがわかる。


これは最小費用流またはハンガリアン法により解ける。

ソースコード
//hungarianはspaghetti sourceのなので略
int conv(char c){
	if(c=='.')return inf;
	if(isdigit(c))return c-'0'+1;
	if(islower(c))return c-'a'+11;
	return c-'A'+37;
}

class SlimeXGrandSlimeAuto {
	public:
	int travel(vector <int> cars, vector <int> districts, vector <string> roads, int iw, int id) 
	{
		int n=cars.size(), m=roads.size(), l=districts.size();
		vector<vi> d(m,vi(m)),walk;
		rep(i,m)rep(j,m){
			d[i][j]=conv(roads[i][j]);
			if(d[i][j]!=inf)d[i][j]*=iw;
		}
		walk=d;
		rep(i,m)walk[i][i]=0;
		rep(k,m)rep(i,m)rep(j,m)walk[i][j]=min(walk[i][j],walk[i][k]+walk[k][j]);
		
		vector<vector<vi> > drive; //drive[i][j][k]=車iを使ってjからkへ行く最短距離
		rep(it,n){
			vector<vi> dd=walk;
			rep(j,m)rep(k,m)dd[j][k]=min(dd[j][k],walk[cars[it]][j]+walk[cars[it]][k]/iw*id);
			
			drive.pb(dd);
		}
		
		vector<vi> M(max(n,l),vi(max(n,l)));
		
		int c=0,cost=0;
		rep(i,l){
			rep(j,n){
				M[j][i]=max(walk[c][districts[i]]-drive[j][c][districts[i]],0);
			}
			cost+=walk[c][districts[i]];
			c=districts[i];
		}
		
		return cost-hungarian(M);
	}
};