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

「AOJ再挑戦86~90」の編集履歴(バックアップ)一覧に戻る

AOJ再挑戦86~90 - (2014/02/04 (火) 18:52:51) の最新版との変更点

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

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

-*Joseph's Potato
-http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0085
-検索したらそのまま答えが出てきた。
-動的計画法らしいのだがよくわからない。
+*問86 Patrol
+http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0086
+一筆書きの判定問題
+
+解法
+一筆書きの判定をそのまま。
 
  #include<stdio.h>
- int f(int n,int k){
- 	return n==1?0:(f(n-1,k)+k)%n;
+ int main(){
+ 	int a,b;
+ 	while(scanf("%d %d",&a,&b)!=EOF){
+ 		int c[255]={0};
+ 		c[a]++;
+ 		c[b]++;
+ 		while(scanf("%d %d",&a,&b)){
+ 			if(a==0&&b==0)break;
+ 			c[a]++;
+ 			c[b]++;
+ 		}
+ 		bool ok=(c[1]%2)&(c[2]%2);
+ 		for(int i=3;i<101;i++){
+  			if(c[i]%2==1)ok=false;
+ 		}
+ 		printf("%s\n",ok?"OK":"NG");
  }
+
+
+
+*問87 Strange Mathematical Expression
+http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0087
+逆ポーランド記法で表記された式を計算する問題
+
+解法
+スタック使った実装ゲーム。
+
+ #include<stdio.h>
+ #include<stack>
+ #include <ctype.h>
+ #include <stdlib.h>
+  
  int main(){
- 	int n,k;
+ 	
  	while(1){
-  		scanf("%d %d",&n,&k);
- 		if((n|k)==0)break;
- 		printf("%d\n",f(n,k)+1);
+ 		char siki[10],c;
+  		double a,b;
+ 		std::stack<double> nums;
+ 		while(scanf("%s%c",siki,&c)!=EOF){
+ 			if(isdigit(siki[0])||siki[1]!='\0'){
+ 				nums.push(atof(siki));
+ 			}else{
+ 				b=nums.top(),nums.pop();
+ 				a=nums.top(),nums.pop();
+ 				switch(siki[0]){
+ 					case '+': nums.push(a+b); break;
+ 					case '-': nums.push(a-b); break;
+  					case '*': nums.push(a*b); break;
+					case '/': nums.push(a/b); break;
+ 				}
+ 			}
+  			if(c=='\n')break;
+ 		}
+ 		printf("%lf\n",nums.top());
+ 		if(scanf("[\n]",&c)==EOF)break;
+ 	}
+ }
+
+
+
+
+*問88 The Code A Doctor Loved
+http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0088
+文字列圧縮の問題。
+
+解法
+対応表を作るくらいしか思いつかないです。
+列を文字列指定してExcelのA列に表をコピペして
+ =CONCATENATE("ctos","['",A1,"']=""",,B1,"""")
+と、あとは\が必要な文字だけ修正すればstd::mapの対応表を作る時間がかかりません。
+それくらいですね。
+あとは2つ目の表はAからZまではビットがきれいに並んでるので自動生成するだけです。
+長いのでカット。
+
+
+
+*問89 The Shortest Path on A Rhombic Path
+http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0089
+菱形の計算。
+
+解法
+一段ずつの動的計画法。
+斜めにしたら縦横だしもうちょっと書きようはあるかな。
+
+ #include<stdio.h>
+ #include<algorithm>
+ #include<string.h>
+ 
+ int main(){
+ 	int row[52]={0};
+  	int oldRowSize=0;
+ 	char c;
+ 	int memo[52]={0};
+ 	while(1){
+ 		int next[52]={0};
+ 		int nowRowSize=0;
+ 		while(scanf("%d%c",&row[nowRowSize],&c)!=EOF){
+ 			nowRowSize++;
+  			if(c=='\n')break;
+ 		}
+ 		for(int i=0;i<nowRowSize-(oldRowSize<nowRowSize);i++){
+ 			next[i]=memo[i]+row[i];
+ 		}
+ 		if(oldRowSize<nowRowSize){
+ 			for(int i=1;i<nowRowSize;i++){
+ 				next[i]=std::max(next[i],memo[i-1]+row[i]);
+ 			}
+  			if(nowRowSize==1)next[0]=row[0];
+ 		}else{
+ 			for(int i=1;i<oldRowSize;i++){
+ 				next[i-1]=std::max(next[i-1],memo[i]+row[i-1]);
+ 			}
+ 		}
+ 		memcpy(memo,next,sizeof(memo));
+ 		if(nowRowSize==1&&nowRowSize<oldRowSize)break;
+  		oldRowSize=nowRowSize;
+ 	}
+ 	printf("%d\n",memo[0]);
+ }
+
+
+
+
+
+
+*問90 Overlaps of Seals
+http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0090
+平面上でシールが最大限重なってる場所を求める問題。
+
+解法
+交点か円の中心だけをチェックすればよいです。
+原点に片方の円の中心を、片方をX軸状にとり交点を求め、これを回転して平行移動して交点を求めます。
+
+
+ #include<stdio.h>
+ #include<vector>
+ #include<math.h>
+  
+ void crossDXY_Sub(double len,double &reX1,double& reY1){
+ 	double herfLen=len/2;
+ 	reX1=herfLen;
+ 	reY1=sqrt(1-herfLen*herfLen);
+ }
+ 
+ void crossDXY(double dx,double dy,double& reX1,double& reY1,double& reX2,double& reY2){
+ 	double x1,y1,len,sinX,cosX;
+  	len=hypot(dx,dy);
+ 	crossDXY_Sub(len,x1,y1);
+	
+ 	sinX=dy/len;
+  	cosX=dx/len;
+ 	reX1=x1*cosX-y1*sinX;
+ 	reY1=x1*sinX+y1*cosX;
+ 	reX2=x1*cosX+y1*sinX;
+ 	reY2=x1*sinX-y1*cosX;
+ }
+ 
+ void calc(int n){
+ 	double xs[101],ys[101];
+ 	std::vector<double> crossX,crossY;
+ 	for(int i=0;i<n;i++){
+ 		scanf("%lf,%lf",&xs[i],&ys[i]);
+ 		crossX.push_back(xs[i]);
+ 		crossY.push_back(ys[i]);
+ 	}
+ 	for(int i=0;i<n;i++){
+ 		for(int j=i+1;j<n;j++){
+ 			double dx=xs[j]-xs[i];
+ 			double dy=ys[j]-ys[i];
+ 			if(dx==0&&dy==0)continue;
+ 			if(dx*dx+dy*dy<=4){
+ 				double x1,x2,y1,y2;
+ 				crossDXY(dx,dy,x1,y1,x2,y2);
+ 				crossX.push_back(x1+xs[i]);
+ 				crossY.push_back(y1+ys[i]);
+ 				crossX.push_back(x2+xs[i]);
+ 				crossY.push_back(y2+ys[i]);
+ 				//printf("(%lf %lf %lf %lf)",x1+xs[i],y1+ys[i],x2+xs[i],y2+ys[i]);
+ 			}
+  		}
+ 	}
+ 	int ans=0;
+ 	for(int i=0;i<crossX.size();i++){
+ 		double x=crossX[i];
+ 		double y=crossY[i];
+ 		int count=0;
+ 		for(int j=0;j<n;j++){
+ 			double dx=xs[j]-x;
+ 			double dy=ys[j]-y;
+ 			if(dx*dx+dy*dy<=1.0000001)count++;
+  		}
+ 		if(ans<count)ans=count;
+ 	}
+ 	printf("%d\n",ans);
+ }
+ 
+ int main(){
+ 	int n;
+  	while(scanf("%d",&n)!=EOF){
+ 		if(n==0)break;
+ 		calc(n);
  	}
  }