※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

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
グラフで表された路線図で駅Aからスタートし駅Pで人と合流して駅Gを目指す時最短時間を求める問題。

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

#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

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

解法
動的計画法で一発です。
二人だけ特別枠から選ぶという部分を上手くルール化できませんでした。
この問題拡張を考えnグループから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
分母がnまでで0~1までの既約分数の数を答えよという問題。

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

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