2291～2300 - c21coterie @ ウィキ

2296 Quest of Merchant

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2296
平面上の街から品物を買って市場で売るとき、市場データから最大利益を求めよという問題。
とりあえずsinapusu2002としてコード実行速度1位をゲット。
コードも一つも記述ミスなく一発で通った。

解法
いくつかの都市を回ることを決めた時どの順序で回っても、一番短い時間で都市を回るルート以外意味がないので最初にこれを無視します。
次にその都市巡回ルートのなかで一番安く商品を買える都市以外から商品を買わないことにします。
この条件で各ルートごとに動的計画法で最短時間と最大利益を計算します。
このルート一つ一つを一単位(市場から出発して都市を回って帰ってくるルートを１セット)としてナップザック法適用すれば高速に答えがもとまります。
この問題応用を考え、都市の数が増えた場合、最短ルートの検索も動的計画法にすればさらに高速になりますがそこまでしなくても十分でしたので最短時間ルートの探索は全探索しております。

#include<stdio.h>
#include<map>
#include<set>
#include<iostream>
#include<string>
#include<string.h>
struct Goods{
	std::string str;
	int w,v;
	bool operator<(const Goods& g)const{
		return str<g.str;
	}
};

int n,m,w,t;
int xs[10]={0},ys[10]={0};
std::map<int,int> times;//keyはbitの立ってる都市を回る順路の最小移動時間
std::set<Goods> goods;
std::map<int,std::set<Goods> > cityGoods;
std::map<int,long long int> riekiMemo;

int cityTime(int x1,int y1,int x2,int y2){
	return (x1<x2?x2-x1:x1-x2)+(y1<y2?y2-y1:y1-y2);
}
 
void saiki(int perm,int time,int cityNo){
	int lastTime=time+cityTime(0,0,xs[cityNo],ys[cityNo]);
if(lastTime>t)return ;
	if(times.find(perm)==times.end()){
		if(perm!=0)times[perm]=lastTime;
	}else if(times[perm]>lastTime){
		times[perm]=lastTime;
	}
	int bit=1;
	for(int i=1;i<=n;i++){
		if((perm&bit)==0){
			saiki(perm+bit,time+cityTime(xs[i],ys[i],xs[cityNo],ys[cityNo]),i);
		}
		bit*=2;
	}
} 
long long int riekiCalc(int cityPerm){
	int bit=1;
	Goods g,g2;
	std::set<Goods> gList;
	std::set<Goods>::iterator it;
	for(int i=0;i<n;i++){
		if((cityPerm&bit)!=0){
			for(it=cityGoods[bit].begin();it!=cityGoods[bit].end();it++){
				g=(*it);
				if(gList.find(g)==gList.end()){
					gList.insert(g);
				}else{
					g2=(*(gList.find(g)));
					if(g.v>g2.v){
						gList.erase(g2);
						gList.insert(g);
					}
				}
			}
		}
		bit*=2;
	}
	long long int rieki[10001];
	memset(rieki,-1,sizeof(rieki));
	rieki[0]=0;
	for(it=gList.begin();it!=gList.end();it++){
		for(int i=0;i<=w-(*it).w;i++){
			if(rieki[i]==-1)continue;
			if(rieki[i+(*it).w]<rieki[i]+(*it).v)rieki[i+(*it).w]=rieki[i]+(*it).v;
		}
	}
	long long int ans=0;
	for(int i=0;i<=w;i++){
		if(rieki[i]>ans)ans=rieki[i];
	}
	return ans;
}

int main(){
	scanf("%d %d %d %d",&n,&m,&w,&t);
	Goods g;
	std::string gName;
	for(int i=0;i<m;i++){
		std::cin>>g.str>>g.w>>g.v;
		goods.insert(g);
	}
	int L,b=1;
	for(int i=1;i<=n;i++){
		scanf("%d %d %d",&L,&xs[i],&ys[i]);
		for(int j=0;j<L;j++){
			std::cin>>g.str>>g.v;
			g.w=(*(goods.find(g))).w;
			g.v=(*(goods.find(g))).v-g.v;
			if(g.v>0)cityGoods[b].insert(g);
		}
		b*=2;
	}
	saiki(0,0,0);
	for(std::map<int,int>::iterator it=times.begin();it!=times.end();it++){
		riekiMemo[(*it).first]=riekiCalc((*it).first);
	}
	long long int rieki[10001],ans=0;
	memset(rieki,-1,sizeof(rieki));
	rieki[0]=0;
	for(std::map<int,int>::iterator it=times.begin();it!=times.end();it++){
		int t1=(*it).second;
		long long int r=riekiMemo[(*it).first];
		for(int i=0;i<=t-t1;i++){
			if(rieki[i]==-1)continue;
			if(rieki[i+t1]<rieki[i]+r)rieki[i+t1]=rieki[i]+r;
		}
	}
	for(int i=0;i<=t;i++){
		if(rieki[i]>ans)ans=rieki[i];
	}
	std::cout<<ans<<"\n";
}

2298　Starting Line

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2298
人参を食べて加速する兎がどれだけのタイムでコースを走りきれるかを計算する問題。

解法
加速してないときに人参を手に入れたら即座に使います。
加速中にニンジンを手に入れたらストック、満タンならそくざに人参を使って新しい人参をストックします。
この条件で兎の行動をシミュレートすれば答えとなります。

#include<stdio.h>
#include<iostream>
struct Rabbit{
	int carrot;
	double nextX,x,time;
};

int main(){
	int n,k;
	double t,u,v,L,D;
	std::cin>>n>>k>>t>>u>>v>>L>>D;
	Rabbit r;
 	r.time=D/u;
r.x=D;
 	r.nextX=D+t*v;
r.carrot=0; 
	double ds[201];
	for(int i=1;i<n;i++)std::cin>>ds[i];
	ds[n]=L;//計算を簡単にするためにゴールにもニンジンがあるとする
	int no=1;
	while(no<=n){
		if(r.nextX>ds[no]){
			if(no==n){
				//人参を食べたままゴールを通り越した
				r.time+=(ds[no]-r.x)/v;
				break;
			}
 			if(r.carrot==k){
				//ニンジンがいっぱいなのでそくざに食べる
				r.time+=(ds[no]-r.x)/v;
				r.x=ds[no];
				r.nextX=ds[no]+v*t;
			}else{
				//人参を確保
				r.carrot++;
 			}
			no++;
		}else if(r.nextX==ds[no]){
			//人参切れたところで人参を取って食べた
			r.time+=t;
			r.x=ds[no];
			r.nextX=ds[no]+t*v;
			no++;
 		}else{
			//次のニンジンに届かない
			if(r.carrot==0){
				//ニンジンが切れた状態で次のニンジンかゴールへ
				r.time+=(ds[no]-r.nextX)/u+t;
				r.x=ds[no];
				r.nextX=ds[no]+v*t;
				no++;
			}else{
 				//人参を食べて再加速
				r.time+=t;
				r.x=r.nextX;
				r.nextX=r.x+t*v;
 				r.carrot--;
				//目標変わらず
			}
		}
	}
	printf("%.9lf\n",r.time);
}

2300　Calender Colors

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2300
ｎ個のlab色空間内の点からｍ個選択し、点の間の距離合計が最大化されるようにｍ個点を選ぶという問題。
動的計画法に落とし込むなど賢い方法を思いつかなかったので深さ優先探索で解決。
意外と速度が出た♪

#include<stdio.h>
#include<string.h>
#include<algorithm>
int n,m;
int spents[21];
long double ansMax=0,memo[22][22];
void saiki(int deep,int no,long double sum){
if(n-no<m-deep)return ;
if(deep>=m){
	ansMax=std::max(ansMax,sum);
}else{
	long double next;
	for(int i=no+1;i<n;i++){
		next=sum;
		spents[deep]=i;
		for(int j=0;j<deep;j++){
			next+=memo[i][spents[j]];
		}
		saiki(deep+1,i,next);
	}
}
}
int main(){
long double labs[22][3],temp,allSum=0;
memset(memo,0,sizeof(memo));
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++){
	scanf("%Lf %Lf %Lf",&labs[i][0],&labs[i][1],&labs[i][2]);
	for(int j=0;j<i;j++){
		temp=0;
		for(int l=0;l<3;l++)temp+=(labs[i][l]-labs[j][l])*(labs[i][l]-labs[j][l]);
		memo[i][j]=memo[j][i]=temp;
		allSum+=memo[i][j];
	}
}
for(int i=0;i<n;i++){
	spents[0]=i;
	saiki(1,i,0);
}
printf("%.7Lf\n",ansMax);
}