AOJ141～150

0141　Spiral Pattern

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0141
指定されたサイズの升目にスパイラルパタンを画くという問題。
升目で描きます。

解法
この問題は、曲がるまでに進むマス数を数列化することができれば非常に簡単になるそうです。
私の場合は盤面のパタンを順番に生成するという方法をとりました。
盤面を生成する方法は非常に多くの人がはまるよくない方法だそうです。

#include <stdio.h>
void solve(int);
char map[101][101];
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int move;
int main()
{
int d,n;
scanf("%d",&d);
for(int i=0;i<d;i++)
{
	scanf("%d",&n);
	solve(n);
	if(i!=d-1){
		printf("\n");
	}
	
}
}
void solve(int n)
{
int x=1,y=n,nx,ny;

if(n==1){printf("#\n");return;}


int r=0;

for(int i=0;i<=n;i++){
	for(int j=0;j<=n;j++){
		map[i][j]=' ';
	}
}
map[x][y]='#';

int count;
int count2=0;
while(count2<2){
	nx=x+dx[r];
	ny=y+dy[r];
	if(n>=nx && nx>0 && n>=ny && ny>0){
		count=0;
		for(int i=0;i<4;i++){
			if(map[nx+dx[i]][ny+dy[i]]=='#') count++;
		}
		
		if(count<2){
			map[nx][ny]='#';
			x=nx;
			y=ny;
			count2=0;
		}else{
			r=(r+1)%4;
			count2++;
		}
		
	}else{
		r=(r+1)%4;
		count2++;
	}
}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			printf("%c",map[j][i]);
		}
		printf("\n");
	}
}

0142　Nature of Prime Numbers

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0142
4で割ると3あまる素数nの性質を確認するための問題。

解法
問題の方で実装を指定しているのでそのまま実装します。
途中結果を配列に確保することで少し高速化しました。

#include<stdio.h>
#include<set>
#include<string.h>
void calc(int n){
int t,data[5001],p=0,up,ans[5001];
std::set<int> c1;
memset(ans,0,5001*4);

for(int i=1;i<n;i++){
	t=(i*i)%n;
	if(c1.find(t)==c1.end()){
		c1.insert(t);
		data[p]=t;
		p++;
	}
}
up=(n-1)/2;
for(int i=0;i<p;i++){
	for(int j=0;j<p;j++){
		if(i==j) continue;
		t=data[i]-data[j];
		t+=t<0?n:0;
		t=t>up?n-t:t;
		ans[t]++;
	}
}
for(int i=1;i<=up;i++){
	printf("%d\n",ans[i]);
}
}
int main(){
int n;
scanf("%d",&n);
while(n!=0){
	calc(n);
	scanf("%d",&n);
}
}

0143Altair and Vega

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0143
平面上に三角形と点二つの座標が与えられるので、片方が三角形の中で片方が三角形の外にあるならＯＫ，でないならＮＧと表示するという問題。
解法
三角形の高さが0の場合があるのでそれだけに注意すれば後は、高校数学の教科書通りに解きます。
三角形ＡＢＣと点Ｐ、Ｑとするなら
→AP=s→ＡＢ+ｔ→ＡＣが 0<ｓ+ｔ<1 0<s<1 0<t<1なら三角形の中にあるという公式を使います。

#include<stdio.h>
bool inDelta(double xs[3],double ys[3],double x,double y){
double x1,x2,x3,y1,y2,y3,k,s,t,u;
x1=xs[1]-xs[0];
y1=ys[1]-ys[0];
x2=xs[2]-xs[0];
y2=ys[2]-ys[0];
x3=x-xs[0];
y3=y-ys[0];
k=(x1*y2-x2*y1);
if(k==0){
	return false;
}
s=(y2*x3-x2*y3)/k;
t=(x1*y3-y1*x3)/k;
u=s+t;

if(s<=0.0 || 1.0<=s || t<=0.0 || 1.0<=t || u<=0.0 || 1.0<=u){
	return false;
}else{
	return true;
}
}
int main(){
double xp[3],yp[3],xk,yk,xs,ys;
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
	scanf("%lf %lf %lf %lf %lf %lf %lf %lf %lf %lf",&xp[0],&yp[0],&xp[1],&yp[1],&xp[2],&yp[2],&xk,&yk,&xs,&ys);
	if(inDelta(xp,yp,xs,ys)==inDelta(xp,yp,xk,yk)){
		printf("NG\n");
	}else{
		printf("OK\n");
	}
}
}

0144　Packet Transportation

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0144
インターネットのデータパケット通信を簡素化したモデルが与えられるので、そのモデルでデータパケットが送信先まで届くか判断する問題。

解法
典型的なグラフの問題なのでワーシャルフロイド法を使って解きます。

#include<stdio.h>
#include<string.h>
int map[101][101]; 
void calc(int n){
int t;
for(int y=1;y<=n;y++){
	for(int x=1;x<=n;x++){
		if(map[x][y]==0) continue;
		for(int i=1;i<=n;i++){
			if(map[y][i]==0 || i==x) continue;
			t=map[x][y]+map[y][i];
			if(map[x][i]==0 || t<map[x][i]){
				map[x][i]=t;
			}
		}
	}
}
}
void setMap(int n){
int no,connect,next;
   memset(map,0,101*101*4);
   
   for(int i=0;i<n;i++){
   	scanf("%d %d",&no,&connect);
   	for(int j=0;j<connect;j++){
   		scanf("%d",&next);
   		map[no][next]=1;
   	}
   }
   calc(n);
int m;
   scanf("%d",&m);
   int s,g,tern;
   for(int i=0;i<m;i++){
   	scanf("%d %d %d",&s,&g,&tern);
   	if(map[s][g]<tern && map[s][g]>0){
   		printf("%d\n",map[s][g]+1);
   	}else{
   		printf("NA\n");
   	}
   }
}
int main(){
int n;
scanf("%d",&n);
   setMap(n);
}

0145 Cards

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0145
カードの山を統合していく問題。
この問題、数か月に一度思い出しては３０分ほど挑戦して良くわからないなと思って諦めてたのだけど今日丁寧に整理したら解けた。
とりあえず動的計画法で解いてみて多分私のコードは普通に考えられる理論値。
他の回答者も計算量は理論値行ってるはず。
これより高速化するならよっぽど凄い発想がいると思う。

#include<stdio.h>
#include<vector>
#include<stdlib.h>
#include <string.h>
struct Yama{
	int a,b;
};
std::vector<Yama> yamas;
int ans[101][101];

int calc(int n){
	memset(ans,-1,sizeof(ans));
	for(int i=0;i<n;i++)ans[i][i]=0;
 	for(int i=1;i<=n;i++){
		for(int j=0;j<n-1;j++){
			for(int k=j;k<n-1;k++){
				int l=i+j;
				if(l<1 || n<=l)continue;
				if(ans[j][k]==-1)continue;
				if(ans[k+1][l]==-1)continue;
				int temp=ans[j][k]+yamas[j].a*yamas[k].b*yamas[k+1].a*yamas[l].b+ans[k+1][l];
				if(ans[j][l]==-1 || temp<ans[j][l])ans[j][l]=temp;
			}
		}
	}

	return ans[0][n-1];
} 


int main(){
	int n;
	
	Yama yama;
 	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d %d",&yama.a,&yama.b);
		yamas.push_back(yama);
	}
	
	printf("%d\n",calc(n));
}

0146 Lupin The 4th

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0146
怪盗「ルパン四世」が仲間とともに複数の蔵を破って盗みをするのですがその時最も早く全ての蔵を破るルートを探すという問題。
蔵を破るたびに蔵から盗み出した千両箱の重さぶんだけ移動速度が低下した状態で次の蔵へ行かなくてはいけないのでそこそこ難しい問題です。

解法
この問題を探索でやると最悪15！通りとなります。
枝がりでは計算量が不安になるので、メモ化探索を使います。
ある蔵にいる時、今まで破ってきた蔵のリストが同じで順番が違うだけの経路は一つにまとめることができます。
破ってきた蔵のリストが同じなので持っている千両箱の重さは同じで残りの破らなけらばいけない蔵も同じになります。
となると一番タイムの早い経路以外残す必要はありません。
この性質を利用して不要な計算を抑えます。
解いたときは知りませんでしたがこの方法を世間では動的計画法と呼ぶそうです。
知りませんでした。

#include<stdio.h>
#include<queue>
#include<math.h>
#include<map>
struct timeMemo{
double time,w;
char root[15],count;
};
struct rootMemo{
char nowPoint;
int memo;
bool operator<(const rootMemo r)const{
	if(nowPoint!=r.nowPoint) return nowPoint<r.nowPoint;
	return memo<r.memo;
}
};
void calc(int n){
int nos[15];
double ws[15],lens[15],len,time,w,speed;
std::queue<rootMemo> qu;
std::map<rootMemo,timeMemo> memo;
rootMemo rm,nextRoot;
timeMemo tm,nextTime;

for(int i=0;i<n;i++){
	scanf("%d %lf %lf",&nos[i],&lens[i],&ws[i]);
	ws[i]*=20.0;
	tm.time=0;
	tm.w=ws[i];
	tm.root[0]=i;
	tm.count=0;
	rm.nowPoint=i;
	rm.memo=(1<<i);
	memo[rm]=tm;
	qu.push(rm);
}

int state;

while(qu.empty()==false){
	rm=qu.front();
	nextRoot=qu.front();
	tm=memo[rm];
       nextTime=memo[rm];
       state=rm.memo;
	qu.pop();
	
	
	speed=2000.0/(70.0+tm.w);
	nextTime.count=tm.count+1;
	for(int j=0;j<n;j++){
		if((state&(1<<j))!=0) continue;
			len=fabs(lens[j]-lens[rm.nowPoint]);
			time=len/speed+tm.time;
			w=tm.w+ws[j];
			nextRoot.memo=state|(1<<j);
			nextRoot.nowPoint=j;
			nextTime.time=time;
			nextTime.w=w;
			nextTime.root[tm.count+1]=j;
			if(memo.find(nextRoot)==memo.end()){
				qu.push(nextRoot);
				memo[nextRoot]=nextTime;
			}else if(memo[nextRoot].time>time){
				memo[nextRoot]=nextTime;
			}
	}
}
   int max=(1<<n)-1;
   double ansTime;
   rm.memo=max;
   rm.nowPoint=0;
   nextTime=memo[rm];
   ansTime=nextTime.time;
   for(int i=1;i<n;i++){
       rm.nowPoint=i;
       tm=memo[rm];
       if(ansTime>tm.time){
           ansTime=tm.time;
           nextTime=tm;
       }
   }
   
   
   printf("%d",nos[nextTime.root[0]]);
   for(int i=1;i<n;i++){
       printf(" %d",nos[nextTime.root[i]]);
   }
   printf("\n");
}
int main(){
int n;
scanf("%d",&n);
calc(n);
}

上記コードではコード実行速度が低速だったので
http://d.hatena.ne.jp/shioshiota/20100708/1278593446
http://d.hatena.ne.jp/Respect2D/20101128/1290917225
リンク先を参考に高速化したコードを掲載します。
高速化した代わりにメモリ使用量が増えています。

#include<stdio.h>
#include<math.h>
struct timeMemo{
double time,w;
char root[15],count;
   timeMemo(){
       time=-1;
   }
};
timeMemo memo[1<<15][15];
void calc(int n){
int nos[15];
double ws[15],lens[15],len,speed;
timeMemo tm,nextTime;
for(int i=0;i<n;i++){
	scanf("%d %lf %lf",&nos[i],&lens[i],&ws[i]);
	ws[i]*=20.0;
	tm.time=0;
	tm.w=ws[i];
	tm.root[0]=i;
	tm.count=0;
	memo[1<<i][i]=tm;
}
int max=(1<<n)-1,nextState;
for(int state=1;state<max;state++){
	for(int j=0;j<n;j++){
		if((state&(1<<j))==0) continue;
		tm=memo[state][j];
           nextTime=tm;
		speed=2000.0/(70.0+tm.w);
		nextTime.count=tm.count+1;
		
		for(int k=0;k<n;k++){
			if((state&(1<<k))!=0) continue;
			len=fabs(lens[j]-lens[k]);
			nextTime.time=len/speed+tm.time;
			nextTime.w=tm.w+ws[k];
			nextTime.root[nextTime.count]=k;
			nextState=state|(1<<k);
			if(memo[nextState][k].time>nextTime.time || memo[nextState][k].time<0){
				memo[nextState][k]=nextTime;
			}
		}
	}
}
   
   double ansTime=memo[max][0].time; 
   nextTime=memo[max][0];
   for(int i=1;i<n;i++){
       tm=memo[max][i];
       if(ansTime>tm.time){
           nextTime=tm;
           ansTime=tm.time;
       }
       //printf("%lf\n",tm.time);
   }
   printf("%d",nos[nextTime.root[0]]);
   for(int i=1;i<n;i++){
       printf(" %d",nos[nextTime.root[i]]);
   }
   printf("\n");
}
int main(){
int n;
scanf("%d",&n);
calc(n);
}

0147　Fukushimaken

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0147

解法
賢い方法を思いつかなかったのでコードサイズが膨らみました。
特に参考にならないと思いますので読み飛ばしてください。
順番に試しているだけです。

#include <stdio.h>
void seatDell(int dellTime,int *seats);
bool searchSheat(int *sheats,int man,int stayTime);
int seatCount=17;
int myMax=1000000000;
struct guest{
int arrivalTime;//到着時刻
int heads;//人数
int stayTime;//座ってる時間
int seatInTime;//座れた時間
};
int main()
{
int time=0,seats[17];

struct guest guests[100];
for(int i=0;i<seatCount;i++) seats[i]=0;
for(int i=0;i<100;i++){
	guests[i].arrivalTime=i*5;
	if(i%5==1){
		guests[i].heads=5;
	}else{
		guests[i].heads=2;
	}
	guests[i].stayTime=17*(i%2)+3*(i%3)+19;
}
int p=0;
int dellTime=0;
while(p<100)
{
	while(1)
	{
		if(guests[p].arrivalTime<=time)
		{
			if(searchSheat(seats,guests[p].heads,guests[p].stayTime)==true)
			{
				guests[p].seatInTime=time;
				p++;
			}else
			{
				break;
			}
		}else
		{
			break;
		}
	}
	if(p>99) break;
	
	for(int i=0;i<seatCount;i++){
		if(dellTime>seats[i] && seats[i]>0) dellTime=seats[i];
	}
	if(time<guests[p].arrivalTime){
		if(dellTime>guests[p].arrivalTime-time) dellTime=guests[p].arrivalTime-time;
	}
	if(dellTime==0){
		dellTime=1;
	}
	time+=dellTime;
	seatDell(dellTime,seats);
}
int t;
while(scanf("%d",&t)!=EOF){
	printf("%d\n",guests[t].seatInTime-guests[t].arrivalTime);
}

}
bool searchSheat(int *seats,int man,int stayTime){
bool seatInFlag=false;
for(int i=0;i<seatCount-man+1;i++){
	seatInFlag=true;
	for(int j=0;j<man;j++){
		if(seats[i+j]!=0){
			seatInFlag=false;
		}
	}
	if(seatInFlag==true){
		for(int j=0;j<man;j++){
			seats[i+j]=stayTime;
		}
		return true;
	}
}
return false;
}
void seatDell(int dellTime,int *seats){
int t;
for(int i=0;i<seatCount;i++){
	t=seats[i]-dellTime;
	if(t>=0){
		seats[i]=t;
	}else{
		seats[i]=0;
	}
}
}

0148　Candy and Class Flag

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0148
学校のクラスで「クラス旗」を保管する生徒を決める問題。
解法
非常に簡単な問題なので書くだけです。

#include<stdio.h>
int main(){
int n;
while(scanf("%d",&n)>0){
	printf("3C%02d\n",(n-1)%39+1);
}
}

0149 Eye Test

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0149
視力検査の結果をランクに分けて集計せよという問題。
解法
簡単な問題なのでＭａｐを使って集計するだけです。

#include<stdio.h>
#include<map>
int main(){
std::map<double,int> Rank;
double r,l;
int Lsum[4]={0,0,0,0},Rsum[4]={0,0,0,0};
Rank[2.1]=0;
Rank[1.1]=1;
Rank[0.6]=2;
Rank[0.2]=3;
while(scanf("%lf %lf",&l,&r)>0){
	Lsum[(*Rank.upper_bound(l)).second]++;
	Rsum[(*Rank.upper_bound(r)).second]++;
}
for(int i=0;i<4;i++){
	printf("%d %d\n",Lsum[i],Rsum[i]);
}
}

0150　Twin Prime

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0150&lang=jp
ｎ以下の最も大きな双子素数を表示せよという問題。

解法
双子素数は6ｎ-1と6ｎ+1になるという性質を使って気持ち高速化しました。
素数の世界は奥が深いので素数を求めるテクニックは無数にありますが、練習問題程度なら大体素朴な手法で解けます。

#include <stdio.h>
int main()
{
bool map[5005];
for(int i=0;i<5005;i++){
	map[i]=true;
}

for(int i=3;i<103;i+=2){
	for(int j=3*i;j<10001;j+=i*2){
		map[j/2-1]=false;
	}
}
int n;
scanf("%d",&n);
while(n!=0){
	if(n<7){
		printf("3 5\n");
	}else{
		n-=n%6==0?6:n%6;
		for(int i=n;i>=0;i-=6){
			if(map[(i-1)/2-1]==true && map[(i+1)/2-1]==true){
				printf("%d %d\n",i-1,i+1);
				break;
			}
		}
	}
	scanf("%d",&n);
}
}

タグ：

+ タグ編集

「AOJ141～150」をウィキ内検索

最終更新：2013年10月12日 09:06

c21coterie @ ウィキ

更新履歴

メニュー

リンク

他のサービス

0141　Spiral Pattern

0142　Nature of Prime Numbers

0143Altair and Vega

0144　Packet Transportation

0145 Cards

0146 Lupin The 4th

0147　Fukushimaken

0148　Candy and Class Flag

0149 Eye Test

0150　Twin Prime

c21coterie @ ウィキ

AOJ141～150

更新履歴

メニュー

リンク

他のサービス

0141 Spiral Pattern

0142 Nature of Prime Numbers

0143Altair and Vega

0144 Packet Transportation

0145 Cards

0146 Lupin The 4th

0147 Fukushimaken

0148 Candy and Class Flag

0149 Eye Test

0150 Twin Prime

0141　Spiral Pattern

0142　Nature of Prime Numbers

0144　Packet Transportation

0147　Fukushimaken

0148　Candy and Class Flag

0150　Twin Prime