「aoj2281～2290」の編集履歴（バックアップ）一覧はこちら

aoj2281～2290 - (2013/02/08 (金) 14:36:55) の１つ前との変更点

追加された行は緑色になります。

削除された行は赤色になります。

*2281　Swap Cipher
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2281
暗号化された文書を復元する問題。

解法
一番簡単な部類の問題なので何も考えずに実装します。
一度全部読んで逆操作で復元しましたが、手前からリニアに読みこんで処理する方法でコンパクトなアルゴリズムを考えつきませんでした。


 #include<stdio.h>
 #include<algorithm> 
 void calc(int n){
 	char text[110];
 	int as[101],bs[101];
 	scanf("%s",text);
 	for(int i=0;i<n;i++)scanf("%d %d",&as[i],&bs[i]);
 	for(int i=n-1;i>=0;i--){
 		char sa=(bs[i]-as[i])%26;
 		char c1=text[as[i]-1]-'a';
 		char c2=text[bs[i]-1]-'a';
 		c1=(c1+sa)%26+'a';
 		c2=(c2+sa)%26+'a';
 		text[as[i]-1]=c2;
 		text[bs[i]-1]=c1;
 	}
 	printf("%s\n",text);
 }
 
 int main(){
 	int n;
 	while(1){
 		scanf("%d",&n);
 		if(n==0)break;
 		calc(n);
 	}
 }





*2283　Seishun 18 Kippu
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2283
グラフで表された路線図で駅Ａからスタートし駅Pで人と合流して駅Ｇを目指す時最短時間を求める問題。

解法
何も考えずダイクストラ法を二回適用するだけです。

 #include<stdio.h>
 #include<string>
 #include<iostream>
 #include<map>
 #include<vector>
 #include<queue>
  
 struct Rosen{
 	std::string str;
 	int time;
 	bool operator<(const Rosen& r)const{
 		return time>r.time;
 	}
 };
 
 int D(std::string s,std::string g,std::map<std::string,std::vector<Rosen> >& G){
 	std::priority_queue<Rosen> qu;
 	Rosen r,nextR;
 	r.time=0;
 	r.str=s;
 	qu.push(r);
 	std::map<std::string,int> timeMemo;
 	while(qu.empty()==false){
 		r=qu.top();
 		qu.pop();
 		if(r.str==g)break;
 		if(timeMemo.find(r.str)!=timeMemo.end()&&timeMemo[r.str]<=r.time)continue;
 		timeMemo[r.str]=r.time;
  		for(std::vector<Rosen>::iterator it=G[r.str].begin();it!=G[r.str].end();it++){
 			nextR.str=(*it).str;
 			nextR.time=r.time+(*it).time;
 			if(timeMemo.find(nextR.str)!=timeMemo.end()&&timeMemo[nextR.str]<=nextR.time)continue;
 			qu.push(nextR);
 		}
 	}
 	return r.time;
 }
 
 void calc(int n,int m){
 	std::string s,p,g,a,b;
 	int d,t;
  	std::map<std::string,std::vector<Rosen> > G;
	std::vector<Rosen> v;
  	std::cin>>s>>p>>g;
 	G[s]=v;
 	G[p]=v;
 	G[g]=v;
 	Rosen r;
 	for(int i=0;i<m;i++){
 		std::cin>>a>>b>>d>>t;
 		if(G.find(a)==G.end())G[a]=v;
 		if(G.find(b)==G.end())G[b]=v;
 		r.str=a;
 		r.time=d/40+t;
 		G[b].push_back(r);
 		r.str=b;
 		G[a].push_back(r);
 	}
 	printf("%d\n",D(s,p,G)+D(p,g,G));
 }
 
 int main(){
 	int n,m;
 	while(1){
 		scanf("%d %d",&n,&m);
 		if(n==0&&m==0)break;
 		calc(n,m);
 	}
 }




*aoj2284　The Legendary Sword
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2284
魔王がフィールドの宝珠を壊しながら伝説の剣に到達するまでの時間を求める問題。

解法
オーソドックスに動的計画法で解きました。
コードの書きやすさを優先した結果余り速度は出てません。


 #include<stdio.h>
 #include<stdlib.h>
 #include<vector>
 #include<map>
 #include<set>
 
 struct P{
 	int x,y;
 	bool operator<(const P& p)const{
 		if(x!=p.x)return x<p.x;
 		return y<p.y;
 	}
 };
 
 int timeCalc(int x1,int y1,int x2,int y2){
 	return (x1>x2?x1-x2:x2-x1)+(y1>y2?y1-y2:y2-y1);
 }
 
 void calc(int w,int h){
 	int gx,gy;
 	char cell[10];
 	std::map<int,std::vector<P> > Os;
 	std::vector<P> v;
 	P p,oldP;
 	int last=1;
 	for(int y=0;y<h;y++){
 		for(int x=0;x<w;x++){
 			scanf("%s",cell);
  			char c=cell[0];
 			if(c=='S'){
 				p.y=y;
 				p.x=x;
 				Os[0]=v;
 				Os[0].push_back(p);
 			}else if(c=='G'){
  				gx=x;
 				gy=y;
 			}else if(c=='.'){
 				//何もしない
 			}else{
 				int no;
 				sscanf(cell,"%d",&no);
 				if(no>=last)last=no+1;
 				p.y=y;
 				p.x=x;
 				if(Os[no].empty()==true)Os[no]=v;
 				Os[no].push_back(p);
 			}
 		}
 	}
 	Os[last]=v;
 	p.x=gx;
 	p.y=gy;
 	Os[last].push_back(p);
	std::map<P,int> memo,next;
 	memo[Os[0][0]]=0;
 	std::map<int,std::vector<P> >::iterator it;
 	for(unsigned int i=1;i<Os.size();i++){
 		for(unsigned int j=0;j<Os[i-1].size();j++){
 			oldP=Os[i-1][j];
 			int time=memo[oldP];
 			for(unsigned int k=0;k<Os[i].size();k++){
 				p=Os[i][k];
 				int nextTime=time+timeCalc(p.x,p.y,oldP.x,oldP.y);
 				if(next.find(p)==next.end()||next[p]>nextTime)next[p]=nextTime;
 			}
 		}
 		memo.clear();
 		memo.insert(next.begin(),next.end());
 		next.clear();
 	}
 	printf("%d\n",(*memo.begin()).second);
 
 } 
 
 int main(){
 	int w,h;
 	while(1){
 		scanf("%d %d",&w,&h);
 		if(w==0&&h==0)break;
 		calc(w,h);
 	}
 }




*2285 Anipero
予算と各メンバの満足度と雇用費が与えられるので満足度を最大にできる呼ぶメンバを選ぶ問題。

解法
動的計画法で一発です。
二人だけ特別枠から選ぶという部分を上手くルール化できませんでした。
この問題拡張を考えｎグループからa1,a2,,,an人を指定して選ぶ場合、動的計画法の部分を関数化して分離する必要があります。

 #include<stdio.h>
 #include<vector>
 #include<string.h>
 
 int memo[102][1002];
 struct A{
 	int e,s;
 };
 
 void calc(int limit,int n,int m,int x){
 	std::vector<A> SEC;
 	A a,a2;
 	int e,s;
 	char name[40];
 	memset(memo,-1,sizeof(memo));
 	memo[0][0]=0;
 	for(int i=0;i<n;i++){
 		scanf("%s %d %d",name,&a.e,&a.s);
 		SEC.push_back(a);
 	}
  	for(int i=1;i<=m;i++){
 		scanf("%s %d %d",name,&e,&s);
 		for(int j=i;j>0;j--){
 			for(int k=limit-e;k>=0;k--){
 				if(memo[j-1][k]==-1)continue;
 				int nextS=memo[j-1][k]+s;
 				if(memo[j][k+e]<=nextS)memo[j][k+e]=nextS;
 			}
 		}
 	}
 	
 	for(int i=x;i<=m;i++){
 		int max=0;
 		int start=0;
 		for(int j=0;j<=limit;j++){
 			if(memo[i][j]!=-1)break;
 			start++;
 		}
 		for(int j=start;j<=limit;j++){
 			if(memo[i][j]>max)max=memo[i][j];
 			else memo[i][j]=max;
 		}
 	}
 	int ans=0;
 	for(int i=0;i<n;i++){
 		a=SEC[i];
 		for(int k=x;k<=m;k++){
 			if(a.e<=limit){
 				int sum=memo[k][limit-a.e];
 				if(sum!=-1){
 					sum+=a.s;
 					if(ans<sum)ans=sum;
 				}
 			}
 		}
 		for(int j=i+1;j<n;j++){
 			a2=SEC[j];
 			for(int k=x;k<=m;k++){
 				if(a.e+a2.e<=limit){
 					int sum=memo[k][limit-a.e-a2.e];
 					if(sum!=-1){
 						sum+=a.s+a2.s;
 						if(ans<sum)ans=sum;
  					}
 				}
 			}
 		}
 	}
 	printf("%d\n",ans);
 }
 
 int main(){
 	int limit,n,m,x;
 	while(1){
 		scanf("%d %d %d %d",&limit,&n,&m,&x);
 		if(limit==0&&n==0&&m==0&&x==0)break;
 		calc(limit,n,m,x);
 	}
 }

*2281　Swap Cipher
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2281
暗号化された文書を復元する問題。

解法
一番簡単な部類の問題なので何も考えずに実装します。
一度全部読んで逆操作で復元しましたが、手前からリニアに読みこんで処理する方法でコンパクトなアルゴリズムを考えつきませんでした。


 #include<stdio.h>
 #include<algorithm> 
 void calc(int n){
 	char text[110];
 	int as[101],bs[101];
 	scanf("%s",text);
 	for(int i=0;i<n;i++)scanf("%d %d",&as[i],&bs[i]);
 	for(int i=n-1;i>=0;i--){
 		char sa=(bs[i]-as[i])%26;
 		char c1=text[as[i]-1]-'a';
 		char c2=text[bs[i]-1]-'a';
 		c1=(c1+sa)%26+'a';
 		c2=(c2+sa)%26+'a';
 		text[as[i]-1]=c2;
 		text[bs[i]-1]=c1;
 	}
 	printf("%s\n",text);
 }
 
 int main(){
 	int n;
 	while(1){
 		scanf("%d",&n);
 		if(n==0)break;
 		calc(n);
 	}
 }





*2283　Seishun 18 Kippu
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2283
グラフで表された路線図で駅Ａからスタートし駅Pで人と合流して駅Ｇを目指す時最短時間を求める問題。

解法
何も考えずダイクストラ法を二回適用するだけです。

 #include<stdio.h>
 #include<string>
 #include<iostream>
 #include<map>
 #include<vector>
 #include<queue>
  
 struct Rosen{
 	std::string str;
 	int time;
 	bool operator<(const Rosen& r)const{
 		return time>r.time;
 	}
 };
 
 int D(std::string s,std::string g,std::map<std::string,std::vector<Rosen> >& G){
 	std::priority_queue<Rosen> qu;
 	Rosen r,nextR;
 	r.time=0;
 	r.str=s;
 	qu.push(r);
 	std::map<std::string,int> timeMemo;
 	while(qu.empty()==false){
 		r=qu.top();
 		qu.pop();
 		if(r.str==g)break;
 		if(timeMemo.find(r.str)!=timeMemo.end()&&timeMemo[r.str]<=r.time)continue;
 		timeMemo[r.str]=r.time;
  		for(std::vector<Rosen>::iterator it=G[r.str].begin();it!=G[r.str].end();it++){
 			nextR.str=(*it).str;
 			nextR.time=r.time+(*it).time;
 			if(timeMemo.find(nextR.str)!=timeMemo.end()&&timeMemo[nextR.str]<=nextR.time)continue;
 			qu.push(nextR);
 		}
 	}
 	return r.time;
 }
 
 void calc(int n,int m){
 	std::string s,p,g,a,b;
 	int d,t;
  	std::map<std::string,std::vector<Rosen> > G;
	std::vector<Rosen> v;
  	std::cin>>s>>p>>g;
 	G[s]=v;
 	G[p]=v;
 	G[g]=v;
 	Rosen r;
 	for(int i=0;i<m;i++){
 		std::cin>>a>>b>>d>>t;
 		if(G.find(a)==G.end())G[a]=v;
 		if(G.find(b)==G.end())G[b]=v;
 		r.str=a;
 		r.time=d/40+t;
 		G[b].push_back(r);
 		r.str=b;
 		G[a].push_back(r);
 	}
 	printf("%d\n",D(s,p,G)+D(p,g,G));
 }
 
 int main(){
 	int n,m;
 	while(1){
 		scanf("%d %d",&n,&m);
 		if(n==0&&m==0)break;
 		calc(n,m);
 	}
 }




*aoj2284　The Legendary Sword
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2284
魔王がフィールドの宝珠を壊しながら伝説の剣に到達するまでの時間を求める問題。

解法
オーソドックスに動的計画法で解きました。
コードの書きやすさを優先した結果余り速度は出てません。


 #include<stdio.h>
 #include<stdlib.h>
 #include<vector>
 #include<map>
 #include<set>
 
 struct P{
 	int x,y;
 	bool operator<(const P& p)const{
 		if(x!=p.x)return x<p.x;
 		return y<p.y;
 	}
 };
 
 int timeCalc(int x1,int y1,int x2,int y2){
 	return (x1>x2?x1-x2:x2-x1)+(y1>y2?y1-y2:y2-y1);
 }
 
 void calc(int w,int h){
 	int gx,gy;
 	char cell[10];
 	std::map<int,std::vector<P> > Os;
 	std::vector<P> v;
 	P p,oldP;
 	int last=1;
 	for(int y=0;y<h;y++){
 		for(int x=0;x<w;x++){
 			scanf("%s",cell);
  			char c=cell[0];
 			if(c=='S'){
 				p.y=y;
 				p.x=x;
 				Os[0]=v;
 				Os[0].push_back(p);
 			}else if(c=='G'){
  				gx=x;
 				gy=y;
 			}else if(c=='.'){
 				//何もしない
 			}else{
 				int no;
 				sscanf(cell,"%d",&no);
 				if(no>=last)last=no+1;
 				p.y=y;
 				p.x=x;
 				if(Os[no].empty()==true)Os[no]=v;
 				Os[no].push_back(p);
 			}
 		}
 	}
 	Os[last]=v;
 	p.x=gx;
 	p.y=gy;
 	Os[last].push_back(p);
	std::map<P,int> memo,next;
 	memo[Os[0][0]]=0;
 	std::map<int,std::vector<P> >::iterator it;
 	for(unsigned int i=1;i<Os.size();i++){
 		for(unsigned int j=0;j<Os[i-1].size();j++){
 			oldP=Os[i-1][j];
 			int time=memo[oldP];
 			for(unsigned int k=0;k<Os[i].size();k++){
 				p=Os[i][k];
 				int nextTime=time+timeCalc(p.x,p.y,oldP.x,oldP.y);
 				if(next.find(p)==next.end()||next[p]>nextTime)next[p]=nextTime;
 			}
 		}
 		memo.clear();
 		memo.insert(next.begin(),next.end());
 		next.clear();
 	}
 	printf("%d\n",(*memo.begin()).second);
 
 } 
 
 int main(){
 	int w,h;
 	while(1){
 		scanf("%d %d",&w,&h);
 		if(w==0&&h==0)break;
 		calc(w,h);
 	}
 }




*2285 Anipero
予算と各メンバの満足度と雇用費が与えられるので満足度を最大にできる呼ぶメンバを選ぶ問題。

解法
動的計画法で一発です。
二人だけ特別枠から選ぶという部分を上手くルール化できませんでした。
この問題拡張を考えｎグループからa1,a2,,,an人を指定して選ぶ場合、動的計画法の部分を関数化して分離する必要があります。

 #include<stdio.h>
 #include<vector>
 #include<string.h>
 
 int memo[102][1002];
 struct A{
 	int e,s;
 };
 
 void calc(int limit,int n,int m,int x){
 	std::vector<A> SEC;
 	A a,a2;
 	int e,s;
 	char name[40];
 	memset(memo,-1,sizeof(memo));
 	memo[0][0]=0;
 	for(int i=0;i<n;i++){
 		scanf("%s %d %d",name,&a.e,&a.s);
 		SEC.push_back(a);
 	}
  	for(int i=1;i<=m;i++){
 		scanf("%s %d %d",name,&e,&s);
 		for(int j=i;j>0;j--){
 			for(int k=limit-e;k>=0;k--){
 				if(memo[j-1][k]==-1)continue;
 				int nextS=memo[j-1][k]+s;
 				if(memo[j][k+e]<=nextS)memo[j][k+e]=nextS;
 			}
 		}
 	}
 	
 	for(int i=x;i<=m;i++){
 		int max=0;
 		int start=0;
 		for(int j=0;j<=limit;j++){
 			if(memo[i][j]!=-1)break;
 			start++;
 		}
 		for(int j=start;j<=limit;j++){
 			if(memo[i][j]>max)max=memo[i][j];
 			else memo[i][j]=max;
 		}
 	}
 	int ans=0;
 	for(int i=0;i<n;i++){
 		a=SEC[i];
 		for(int k=x;k<=m;k++){
 			if(a.e<=limit){
 				int sum=memo[k][limit-a.e];
 				if(sum!=-1){
 					sum+=a.s;
 					if(ans<sum)ans=sum;
 				}
 			}
 		}
 		for(int j=i+1;j<n;j++){
 			a2=SEC[j];
 			for(int k=x;k<=m;k++){
 				if(a.e+a2.e<=limit){
 					int sum=memo[k][limit-a.e-a2.e];
 					if(sum!=-1){
 						sum+=a.s+a2.s;
 						if(ans<sum)ans=sum;
  					}
 				}
 			}
 		}
 	}
 	printf("%d\n",ans);
 }
 
 int main(){
 	int limit,n,m,x;
 	while(1){
 		scanf("%d %d %d %d",&limit,&n,&m,&x);
 		if(limit==0&&n==0&&m==0&&x==0)break;
 		calc(limit,n,m,x);
 	}
 }








*2286 Farey Sequence
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2286
分母がｎまでで0～１までの既約分数の数を答えよという問題。

解法
オーソドックスにファイ関数を使って下から足し上げてみました。
数学の知識がないために速度出てません。

 #include<stdio.h>
 #include<iostream>
 long long int phiTable[1000*1000+1];
 
 int phi(int n){
 	double re=n;
 	for(int i=2;i*i<=n;i+=(i&1)+1){
  		int p=i;
 		int count=0;
 		while(n%p==0){
 			n/=p;
 			count++;
  		}
 		if(count>0)re*=(1-1.0/p);
 	}
 	if(n!=1)re*=(1-1.0/n);
 	return (int)re+0.5;
 }
 
 int main(){
 	phiTable[1]=2;
 	phiTable[2]=3;
 	phiTable[3]=5;
  	long long int sum=5;
 	for(int i=4;i<=1000000;i++){
 		sum+=phi(i);
 		phiTable[i]=sum;
 	}
 	int n,t;
 	scanf("%d",&n);
 	for(int i=0;i<n;i++){
 		scanf("%d",&t);
 		std::cout<<phiTable[t]<<"\n";
 	}
 }