AOJ211～220

0211　Jogging

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0211
生徒が学校でジョギングをします。
学校からでて各々のコースを通り学校に戻ってくることを繰り返します。
各人のコースの長さと速度が与えられます。
全員が同時に学校をスタートして次にそろうのは各人が何周した時かを答える問題です。

解法
一人目と二人目がともに戻ってくるタイミングを分数で求めaとします。
以後この二人はaの倍数でそろうので、aを一人の人とみなして次の人と揃う時を求めます。
これを人数分繰り返します。
全員がそろう周回数が分かれば後は各人が何周でそのタイミングになるかを求めるだけです。
実装は再帰で行い答えは逆順で求まるのでスタックを使いました。
もう少し賢い実装があるかもしれません。

#include<stdio.h>
#include<algorithm>
#include<stack>
std::stack<long long int> ansMemo;
long long int gcd(long long int x,long long int y){
if(y>x) std::swap(x,y);
int count=0;
while(y>0){
	x=x%y;
	std::swap(x,y);
}
return x;
}
int n;
long long int fd,fv;
long long int saiki(int deep,long long int d,long long int v,long long int roop){
   if(deep==n){
       return roop;
   }
   long long int d1,v1,nd,nv,m,n,r,ans;
   scanf("%lld %lld",&d1,&v1);
   m=v*d1;
   n=d*v1;
   m/=gcd(m,n);
   r=saiki(deep+1,d*m,v,roop*m);
   ans=(fd*r*v1)/(v*d1);
   ansMemo.push(ans);
   return r;
}
int main(){
   while(scanf("%d",&n),n>0){
       scanf("%lld %lld",&fd,&fv);
       printf("%lld\n",saiki(1,fd,fv,1));
       while(!ansMemo.empty()){
           printf("%lld\n",ansMemo.top());
           ansMemo.pop();
       }
   }
}

0212　Highway Express Bus

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0212
バスの路線図が与えられます。
バスを乗りついて目的地までいくとき、運賃の合計を最小にせよという問題。
路線では半額券を数枚使うことができ、半額券を使った場合を考慮する必要があるという問題。

解法
あまり良い解法を用意できませんでした。
↓リンク先の方がよいコードが掲載されているのでそちらを参考にしてください。
http://program.pinemz.net/article/169960087.html
リンク先の解説。
リンク先の方法は、頂点数最大１００＊残りのチケット枚数０から１０枚までの１１通りの１１００点に対しダイクストラ法を適用しているシンプルなコードです。
いろいろな経路である地点Aについたときどのルートにせよ残りのチケット枚数が同じなら、一番合計運賃の少ないルート以外ルートを残す必要がないということを利用してといています。

私のコードの解法。
拡張ダイクストラ法で半額券を使わなかった場合の最低値経路を求め、この経路に半額を適用しこれを暫定的な解ansとします。
次にワーシャルフロイド法で半額券が無限にあると仮定した場合の２地点間の値段を計算します。
後は深さ優先探索でansを超えない経路を全探索します。
探索中”今いる地点からワーシャルフロイド法で求めたゴールまでの金額+ここまでの合計金額”がansを超えたらどうあがいてもその経路ではans以下の金額でゴールにたどり着くことができなず枝がりします。
探索がゴールにたどり着いたら、合計金額を比べansが記録更新されたらansを書き換えます。

路線数が少ないのでこの方法で上手く行きましたが、路線数が多くなった場合この手法では上手くいきません。
リンク先の方法を参考にした方がよいでしょう。

#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
int herfMap[101][101];
int rootMap[101][101];
bool mapMoveOKs[101];
int mymax=100000000;
int c,n,m,s,d,ans;
void wf(){
int t;
for(int k=1;k<=n;k++){
	for(int i=1;i<=n;i++){
		if(herfMap[i][k]==mymax)continue;
		for(int j=1;j<=n;j++){
			t=herfMap[i][k]+herfMap[k][j];
			if(t<herfMap[i][j])herfMap[i][j]=t;
		}
	}
}
}
void ds(){
bool moveOKs[101];
int moveCost[101],moveRoot[101],min,nowP;
memset(moveOKs,true,101);
for(int i=1;i<=n;i++)moveCost[i]=mymax;
moveCost[s]=0;
while(1){
	min=mymax;
	for(int i=1;i<=n;i++){
		if(min>moveCost[i] && moveOKs[i]==true){
			min=moveCost[i];
			nowP=i;
		}
	}
	if(min==mymax || nowP==d)break;
	moveOKs[nowP]=false;
	
	for(int i=1;i<=n;i++){
		if(moveCost[i]>herfMap[nowP][i]+moveCost[nowP]){
			moveCost[i]=herfMap[nowP][i]+moveCost[nowP];
			moveRoot[i]=nowP;
		}
	}
}
std::vector<int> rootSum;
nowP=d;
while(nowP!=s){
	rootSum.push_back(herfMap[moveRoot[nowP]][nowP]);
	nowP=moveRoot[nowP];
}
std::sort(rootSum.begin(),rootSum.end(),std::greater<int>());
ans=0;
int up=rootSum.size()>c?c:rootSum.size();
for(int i=0;i<up;i++){
	ans+=rootSum[i];
}
for(int i=up;i<rootSum.size();i++){
	ans+=rootSum[i]*2;
}
}
void search(std::priority_queue<int,std::vector<int>,std::greater<int> > qu,int deep,int sum,int add,int nowP){
sum+=add;
if(add!=0)qu.push(add);
if(c<deep){
	sum+=qu.top();
	qu.pop();
}
if(nowP==d){
	ans=ans>sum?sum:ans;
	return;
}
if(sum+herfMap[nowP][d]>=ans)return;	
for(int i=1;i<=n;i++){
	if(mapMoveOKs[i]==true && rootMap[nowP][i]<mymax){
		mapMoveOKs[i]=false;
		search(qu,deep+1,sum,rootMap[nowP][i],i);
		mapMoveOKs[i]=true;
	}
}
}
void setMap(){
for(int i=1;i<=n;i++){
	for(int j=1;j<=n;j++){
		rootMap[i][j]=herfMap[i][j]=mymax;
	}
}
int p1,p2,cost;
for(int i=0;i<m;i++){
	scanf("%d %d %d",&p1,&p2,&cost);
	rootMap[p1][p2]=rootMap[p2][p1]=herfMap[p1][p2]=herfMap[p2][p1]=cost/2;
}
memset(mapMoveOKs,true,101);
ds();
wf();
std::priority_queue<int,std::vector<int>,std::greater<int> > qu;
search(qu,0,0,0,s);
printf("%d\n",ans);
}
int main(){
while(1){
	scanf("%d %d %d %d %d",&c,&n,&m,&s,&d);
	if(c+n+m+s+d==0) break;
	setMap();
}
}

0213　Subdivide The Land

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0213
土地の区分けデータから区画分けする方法が一通りに定まるか判別する問題。

解法
賢い方法を思いつかないので土地区画の全ての組み合わせを深さ優先探索で全探索します。

#include <stdio.h>
#include <map>
void solve(int x,int y,int n);
void search(int deep);
void myPrint();
int x,y,n;
int ansCount=0;
std::map<int,int> sizeDataTemp;//所有者情報がランダムに備えてのソート用
std::map<int,int>::iterator it;
int sizeData[16];
int map[11][11];
int ansMap[11][11];
int bs[16],ks[16];//メモデータ
int xs[16],ys[16];//各所有者の看板の位置
int main()
{
scanf("%d %d %d",&x,&y,&n);
while(x!=0 && y!=0 && n!=0){
	solve(x,y,n);
	scanf("%d %d %d",&x,&y,&n);
}
} 
void solve(int x,int y,int n)
{
ansCount=0;
int t1,t2;
for(int i=0;i<n;i++){
	scanf("%d %d",&t1,&t2);
	sizeDataTemp[t1]=t2;
}
it=sizeDataTemp.begin();
int i=0;
while(it!=sizeDataTemp.end()){
	sizeData[i]=(*it).second;
	it++;
	i++;
}
for(int i=0;i<y;i++){
	for(int j=0;j<x;j++){
		scanf("%d",&map[i][j]);
		if(map[i][j]>0){
			xs[map[i][j]-1]=j;
			ys[map[i][j]-1]=i;
		}
	}
}	
search(0);
if(ansCount==1){
	myPrint();
}else{
	printf("NA\n");
}
}
void myPrint(){
for(int i=0;i<y;i++){
	for(int j=0;j<x;j++){
		printf("%d",ansMap[i][j]);
		if(j==x-1){
			printf("\n");
		}else{
			printf(" ");
		}
	}
}
}
void search(int deep){
if(deep==n){
	ansCount++;
	for(int i=0;i<y;i++){
		for(int j=0;j<x;j++){
			ansMap[i][j]=map[i][j];
		}
	}
	return ;
}	
for(int i=1;i<=sizeData[deep];i++)
{
	if(sizeData[deep]%i!=0) continue;//長方形が作れなかったので駄目
	//一つずつ範囲をずらしながら試す。
	int xSize=i,ySize=sizeData[deep]/i;
	for(int sy=ys[deep]-ySize+1;sy<=ys[deep];sy++)
	{
		for(int sx=xs[deep]-xSize+1;sx<=xs[deep];sx++)
		{
			if(sy<0) break;
			if(sy+ySize-1>=y || sx+xSize-1>=x) break;
			if(sx<0) continue;
			bool inOKFlag=true;
			for(int j=sy;j<sy+ySize;j++){
				for(int k=sx;k<sx+xSize;k++){
					if(map[j][k]!=0 && map[j][k]!=deep+1){
						inOKFlag=false;
						break;
					}
				}
				if(inOKFlag==false) break;
			}				
			if(inOKFlag==true){
				for(int j=sy;j<sy+ySize;j++){
					for(int k=sx;k<sx+xSize;k++){
						map[j][k]=deep+1;
					}
				}
				search(deep+1);
				if(ansCount>1) return;
				for(int j=sy;j<sy+ySize;j++){
					for(int k=sx;k<sx+xSize;k++){
						if(!(j==ys[deep] && k==xs[deep])){
							map[j][k]=0;
						}
					}
				}
			}
		}
	}
}
}

0214　Autumnal Illumination

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0214
平面上に配置される凸四角形型のイルミネーションをつなげていくとき何個電源がいるかを求める問題。
接するか共有部分を持つイルミネーションは一つの電源で全てつながるとみて電源の個数を求めます。

解法
２つの四角形が交点を持つがどの点も相手の四角形の中に入らない。
２つの四角形を比較した時、相手の四角形の中に点が入る。
この二つをチェックすればつながりが分かるのでそのつながりをグラフに入れていきます。
２つの四角形が一点を共有する場合もつながっているとみなすことに注意します。

四角形の中に点があるかのチェック方法。
凸四角形の頂点を時計回りにＡＢＣＤとし、ＡＢＣＤの中にあるか調べたい点をＰとします。
ＡＰのような表記をベクトルＡＰとしＡＰ*ＡＢをＡＰとＡＢの外積と定義します。
Ｇ1＝ＡＰ*ＡＢ
Ｇ2＝ＢＰ*ＢＣ
Ｇ3＝ＣＰ*ＣＤ
Ｇ4＝ＤＰ*ＤＡ
Ｇ1，Ｇ２，Ｇ3，Ｇ4＜＝0かＧ1、Ｇ2，Ｇ3，Ｇ4＞＝0を満たせば点ＰはＡＢＣＤの中にあると判断できます。

２つの四角形が交点を持つかのチェックはcrossCheck関数で行い、２つの線分が交点を持つかの判別式をそのまま使います。

#include<stdio.h>
#include<string.h>
bool g[101][101];
bool moveOKs[101];
void saiki(int now,int m){
moveOKs[now]=false;
for(int i=0;i<m;i++){
	if(moveOKs[i] && g[now][i]){
		saiki(i,m);
	}
}
}
bool crossCheck(int xs[4],int ys[4],int xs2[4],int ys2[4]){
int vx,vy,vx2,vy2,t1,t2,t3,t4,c,c2;
for(int i=0;i<4;i++){
	vx=xs[(i+1)%4]-xs[i];
	vy=ys[(i+1)%4]-ys[i];
	c=ys[i]*vx-xs[i]*vy;
	for(int j=0;j<4;j++){
		t1=vy*xs2[j]-vx*ys2[j]+c;
		t2=vy*xs2[(j+1)%4]-vx*ys2[(j+1)%4]+c;
		vx2=xs2[(j+1)%4]-xs2[j];
		vy2=ys2[(j+1)%4]-ys2[j];
		c2=ys2[j]*vx2-xs2[j]*vy2;
		t3=vy2*xs[i]-vx2*ys[i]+c2;
		t4=vy2*xs[(i+1)%4]-vx2*ys[(i+1)%4]+c2;
		if(t1==0 && t2==0)continue;
		if(t3==0 && t4==0)continue;//同一直線状にあるのでunionCheckまで判断を保留する
		if(t1*t2<=0 && t3*t4<=0){
			return true;
		}
	}
}
return false;
}
bool unionCheck(int xs[4],int ys[4],int x,int y){
//外積の符号が一定なら点(x,y)は四角形の中にある
int vx1,vy1,vx2,vy2,rs[4],d;
for(int i=0;i<4;i++){
	vx1=xs[(i+1)%4]-xs[i];
	vy1=ys[(i+1)%4]-ys[i];
	vx2=x-xs[i];
	vy2=y-ys[i];
	rs[i]=vx1*vy2-vx2*vy1;
	if(rs[i]!=0)d=rs[i];
}
for(int i=0;i<4;i++){
	if(!((d<0 && rs[i]<=0)||(d>0&&rs[i]>=0))){
		return false;
	}
}
return true;
}
void setData(int m){
memset(g,false,101*101);
memset(moveOKs,true,101);
int xs[101][4],ys[101][4];
bool in1,in2,in3;
for(int i=0;i<m;i++){
	for(int j=0;j<4;j++){
		//イルミネーションのデータをセットする
		scanf("%d %d",&xs[i][j],&ys[i][j]);
	}
	for(int j=0;j<i;j++){
		//イルミネーションiとｊが交点を持つかをチェックする
		in3=crossCheck(xs[i],ys[i],xs[j],ys[j]);
		for(int k=0;k<4;k++){
			//イルミネーションiとjがどちらかの中にあるかをチェックする
			in1=unionCheck(xs[j],ys[j],xs[i][k],ys[i][k]);
			in2=unionCheck(xs[i],ys[i],xs[j][k],ys[j][k]);
			if(in1||in2||in3){
				g[i][j]=g[j][i]=true;
				break;
			}
		}
	}
}
int count=0;
for(int i=0;i<m;i++){
	if(moveOKs[i]){
		count++;
		saiki(i,m);
	}
}
printf("%d\n",count);
}
int main(){
int n,m;
while(1){
	scanf("%d",&n);
	if(n==0) break;
	for(int i=0;i<n;i++){
		scanf("%d",&m);
		setData(m);
	}
}
}

0215　Pachimon Creature

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0215
マップ上にいるパチモンモンスターを効率よく回収していく問題。

解法
グラフの問題とみて特定のパチモンから初めて動的計画法で解きます。
n種類目のあるパチモンをゲットした時、そのパチモンをゲットできる経路の中で一番短い距離だけを残して他は削除します。
これによって計算量を抑えます。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int xs[5][1001],ys[5][1001],ps[5],sx,sy,gx,gy,ansCalc[4][1001];
int ans,ansType;
void saiki(int deep,int now,int type){
int t,old=(now+4)%5;
if(ps[now]==0 && deep!=4)return;
if(deep==0){
	for(int i=0;i<ps[now];i++){
		ansCalc[0][i]=abs(sx-xs[now][i])+abs(sy-ys[now][i]);
	}
	saiki(deep+1,(now+1)%5,type);
}else if(deep==4){
	for(int i=0;i<ps[old];i++){
		t=ansCalc[deep-1][i]+abs(xs[old][i]-gx)+abs(ys[old][i]-gy);
		if(ans>t){
			ans=t;
			ansType=type;
		}
	}
}else{
	for(int i=0;i<ps[now];i++){
		for(int j=0;j<ps[old];j++){
			t=ansCalc[deep-1][j]+abs(xs[now][i]-xs[old][j])+abs(ys[now][i]-ys[old][j]);
			if(ansCalc[deep][i]==0 || ansCalc[deep][i]>t){
				ansCalc[deep][i]=t;
			}
		}
	}
	saiki(deep+1,(now+1)%5,type);
}
}
void setData(int x,int y){
char line[1001],t;
memset(ps,0,5*4);
for(int i=0;i<y;i++){
	//パチモンの座標をセットする
	scanf("%s",line);
	for(int j=0;j<x;j++){
		t=line[j];
		if(t=='S'){
			sx=j;
			sy=i;
		}else if(t=='G'){
			gx=j;
			gy=i;
		}else if(t!='.'){
			xs[t-'1'][ps[t-'1']]=j;
			ys[t-'1'][ps[t-'1']]=i;
			ps[t-'1']++;
		}
	}
}
int checkCount=0;
for(int i=0;i<5;i++){
	checkCount+=ps[i]==0?0:1;
}
if(checkCount<4){
	printf("NA\n");
}else{
	ans=1000000000;
	for(int i=0;i<5;i++){
		memset(ansCalc,0,4*1001*4);
		saiki(0,(i+1)%5,i+1);
	}
	printf("%d %d\n",ansType,ans);
}
}
int main(){
int x,y;
while(1){
	scanf("%d %d",&x,&y);
	if(x==0 && y==0) break;
	setData(x,y);
}
}

0216　Cutting Down Water Bills

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

水道料金の計算をする問題。
料金は使用量が増えるごとにリッター頭の値段が増加します。

解法
条件に従って計算するだけです。

#include<stdio.h>
int main(){
int n;
while(scanf("%d",&n),n!=-1){
	printf("%d\n",4280-(n>=30?3800+(n-30)*160:n>=20?2400+(n-20)*140:n>=10?1150+(n-10)*125:1150));
}
}

0217　Walking in the Hospital

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0217
ウォーキングの記録から一番歩いた人のＮｏと歩数を出力する問題。

解法
出題形式に慣れるための問題なので小学生プログラマでも解けるように出来ています。
一番大きな値を記録するだけです。

#include<stdio.h>
int main(){
int n,p,d1,d2,i,ans,max;
while(scanf("%d",&n),n!=0){
	max=0;
	for(i=0;i<n;i++){
		scanf("%d %d %d",&p,&d1,&d2);
		if(max<d1+d2){
			max=d1+d2;
			ans=p;
		}
	}
	printf("%d %d\n",ans,max);
}
}

0218　Dividing Students

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0218
テストの得点に応じて生徒をランク分けする問題。

解法
テストの得点という3次元空間を平面で分割しますがそんな難しいことは考えず定義通りに書くだけです。

#include<stdio.h>
char rank(){
int pm,pe,pj,sum;
scanf("%d %d %d",&pm,&pe,&pj);
sum=pm+pe+pj;

if(pm==100 || pe==100 || pj==100 || pm+pe>=180 || sum>=240) return 'A';
if(sum>=210 || (sum>=150 && (pm>=80 || pe>=80))) return 'B';
return 'C';
}
int main(){
int n;
while(scanf("%d",&n),n>0){
	while(n--){
		printf("%c\n",rank());
	}
}
}

0219　A Popular Ice-cream Shop

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0219
アイスクリーム屋さんの各商品の売り上げを集計する問題。

解法
集計して表示するだけです。
出力をまとめることで気持ち高速化しています。

#include<stdio.h>
void put(int n){
int sums[10],t;
for(int i=0;i<10;i++)sums[i]=0;
for(int i=0;i<n;i++){
	scanf("%d",&t);
	sums[t]++;
}
for(int j=0;j<10;j++){
	if(sums[j]==0){
		printf("-\n");
	}else{
		while(sums[j]>10){
			sums[j]-=10;
			printf("**********");
		}
		for(int i=0;i<sums[j];i++){
			printf("*");
		}
		printf("\n");
	}
}
}
int main(){
int n;
while(scanf("%d",&n),n>0){
	put(n);
}
}

0220　Binary Digit A Doctor Loved

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0220
与えられた数を時整数部8ケタ小数部4ケタの2進数で表せるかを判別する問題。

解法
浮動小数点の小数部分は(1/2)＾ｎであらわせる数同士の足し引きでは計算誤差が発生しないということを利用して、再帰で数を近似して小数部の表示を求めます。
整数部は＆演算で求めます。
この問題double型の構造を上手く使えば短いＢｉｔ演算だけで条件を満たすか判別できるはずですが、そこまで調べる気にはなれませんでした。
興味がある方は調べてみてください。

#include<stdio.h>
const int size=4;
bool ok;
int memo[size];
void calc(int deep,double herf,double l){
if(deep==size){
	ok=l>0?false:true;
	return ;
}
if(herf<=l){
	memo[deep]=1;
	calc(deep+1,herf*0.5,l-herf);
}else{
	memo[deep]=0;
	calc(deep+1,herf*0.5,l);
}

}
int main(){
double l;
int n;
while(scanf("%lf",&l),l!=-1.0){
	n=(int)l;
	ok=true;
	if(n>255){
		ok=false;
	}else{
		calc(0,0.5,l-n);
	}
	if(ok==true){
		for(int i=128;i>=1;i/=2){
			printf("%d",(n&i)==0?0:1);
		}
		printf(".");
		for(int i=0;i<size;i++){
			printf("%d",memo[i]);
		}
		printf("\n");
	}else{
		printf("NA\n");
	}
}
}

タグ：

+ タグ編集

「AOJ211～220」をウィキ内検索

最終更新：2011年09月27日 15:04

c21coterie @ ウィキ

更新履歴

メニュー

リンク

他のサービス

0211　Jogging

0212　Highway Express Bus

0213　Subdivide The Land

0214　Autumnal Illumination

0215　Pachimon Creature

0216　Cutting Down Water Bills

0217　Walking in the Hospital

0218　Dividing Students

0219　A Popular Ice-cream Shop

0220　Binary Digit A Doctor Loved

c21coterie @ ウィキ

AOJ211～220

更新履歴

メニュー

リンク

他のサービス

0211 Jogging

0212 Highway Express Bus

0213 Subdivide The Land

0214 Autumnal Illumination

0215 Pachimon Creature

0216 Cutting Down Water Bills

0217 Walking in the Hospital

0218 Dividing Students

0219 A Popular Ice-cream Shop

0220 Binary Digit A Doctor Loved

0211　Jogging

0212　Highway Express Bus

0213　Subdivide The Land

0214　Autumnal Illumination

0215　Pachimon Creature

0216　Cutting Down Water Bills

0217　Walking in the Hospital

0218　Dividing Students

0219　A Popular Ice-cream Shop

0220　Binary Digit A Doctor Loved