「AOJ再挑戦36～40」の編集履歴（バックアップ）一覧はこちら

「AOJ再挑戦36～40」(2014/01/29 (水) 15:03:03) の最新版変更点

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

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

*問３６ A Figure on Surface
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0036
おかれたブロックを判定する問題。
解法
ブロックの一番上で一番左のブロックを基準に、その右3マス下３マスのブロックの状態をビットにして判断します。
解いたのでほかの人のコードも見ましたが私は平均的なコードでした。
コードの短さ一位のコードはもはや異次元、数学みたいなコードでなにがなにやら？
MOD演算の概念を使ってる雰囲気だけど読み解けなかった。
自分がホビーアルゴリズマーとして３流なんだなと感じるしだい。

 #include<stdio.h>
 #include<string.h>
 
 char blockType(char test[12][12],int r,int c){
 	int pow2=1,sum=0;
 	for(int i=0;i<3;i++){
 		for(int j=0;j<3;j++){
 			if(test[r+i][c+j]=='1'){
 				sum+=pow2;
 			}
 			pow2*=2;
 		}
 	}
 	char re;
 	if(sum==27)re='A';
 	if(sum==73)re='B';
 	if(sum==7)re='C';
 	if(sum==9)re='D';
 	if(sum==51)re='E';
 	if(sum==153)re='F';
 	if(sum==11)re='G';
 	return re;
 }
 
 int main(){
 	char board[12][12];
 	int r,c;
  	memset(board,0,sizeof(board));
 	while(1){
 		r=c=-1;
 		if(scanf("%s",board[0])==EOF)break;
 		for(int i=1;i<8;i++){
 			scanf("%s",board[i]);
  			for(int j=8;j<12;j++)board[i][j]='\0';
 		}
 		
 		for(int i=0;i<8;i++){
 			for(int j=0;j<8;j++){
  				if(r==-1&&board[i][j]=='1'){
 					r=i;
 					c=j;
 				}
  			}
 		}
 		printf("%c\n",blockType(board,r,c));
 	}
 } 




*問37　Path on a Grid
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0037
壁に右手をついて歩く人の移動を表示する問題。


解法
一見混乱する問題ですが
右手を常につけているのですから。
西を向いているときは必ず北の壁に手をつけ
東を向いているときは必ず南の壁に手を付けています。
曲がる方向は東なら、北　東　南　西にもどるの順でその方向へ向かう壁がないか検証します。
他の方向も回転しただけで検証順序が同じです。
次の位置決めに不要な情報を全部取り去るとコード簡素になります。

moveCommit関数を配列にすればもう少し抽象化できるかもしれません。

 #include<stdio.h>
 #include<string.h>
 const int Right=0;
 const int Up=1;
 const int Left=2;
 const int Down=3;
 int moves[4][4]={{Up,Right,Down,Left},
 		 {Left,Up,Right,Down},
 		 {Down,Left,Up,Right},
 		 {Right,Down,Left,Up}};
 char walls[100][100];
 int height=0;
 
 bool is_wall(int x,int y){
 	if(y<0||height<=y)return false;
 	if(x<0||strlen(walls[y])<=x)return false;
 	if(walls[y][x]!='1')return false;
 	return true;
 }
 
 void moveCommit(int x,int y,int r,int &nx,int &ny,int &nr){
 	for(int i=0;i<4;i++){
 		int r1=moves[r][i];
		if(r1==Up){
 			int py=y*2-1;
 			int px=x;
 			if(is_wall(px,py)){
 				nx=x;
 				ny=y-1;
 				nr=Up;
 				return ;
 			}
 		}else if(r1==Right){
 			int py=y*2;
 			int px=x;
  			if(is_wall(px,py)){
 				nx=x+1;
 				ny=y;
 				nr=Right;
 				return;
 			}
 		}else if(r1==Left){
 			int py=y*2;
 			int px=x-1;
 			if(is_wall(px,py)){
 				nx=x-1;
  				ny=y;
 				nr=Left;
 				return;
 			}
 		}else if(r1==Down){
 			int py=y*2+1;
 			int px=x;
 			if(is_wall(px,py)){
 				nx=x;
  				ny=y+1;
 				nr=Down;
 				return;
 			}
 		}
 	}
 }
 
 int main(){
 	int nowX=1,nowY=0,nowR=0,nextX,nextY,nextR;
 	char muki[5]="RULD";
  	
 	for(height=0;scanf("%s",walls[height])!=EOF;height++);
 	printf("R");
 	while(nowX!=0||nowY!=0){
 		moveCommit(nowX,nowY,nowR,nextX,nextY,nextR);
 		printf("%c",muki[nextR]);
 		nowX=nextX;
  		nowY=nextY;
 		nowR=nextR;
 	}
  	printf("\n");
 }




*問38Poker Hand
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0038
簡易ルールのポーカーの役を判定する問題。
解法
yakuPrint1で同じ数字のチェック。
yakuPrint2でストレートのチェック。
それだけ。

 #include<stdio.h>
 #include<algorithm>
 #include <functional>
 
 bool yakuPrint1(int count[14]){
 	std::sort(count,count+14,std::greater<int>());
 	bool printOK=true;
 	if(count[0]==4){
 		printf("four card\n");
 	}else if(count[0]==3&&count[1]==2){
 		printf("full house\n");
 	}else if(count[0]==3){
 		printf("three card\n");
 	}else if(count[0]==2&&count[1]==2){
 		printf("two pair\n");
 	}else if(count[0]==2){
 		printf("one pair\n");
  	}else{
 		printOK=false;
 	}
 	return printOK;
 } 
 bool yakuPrint2(int cards[5]){
 	std::sort(cards,cards+5);
 	bool printOK=true;
 	for(int i=1;i<5;i++){
 		if(cards[i-1]+1!=cards[i])printOK=false;
 	}
 	if(printOK==true){
  		printf("straight\n");
 	}else{
 		if(cards[0]==1&&cards[1]==10&&cards[2]==11&&cards[3]==12&&cards[4]==13){
 			printf("straight\n");
 			printOK=true;
  		}
 	}
 	return printOK;
 }
 
 void yakuPrint(int cards[5],int count[14]){
  	if(yakuPrint1(count)||yakuPrint2(cards)){
 		//何もなし
 	}else{
 		printf("null\n");
  	}
 }
 
 int main(){
  	int cards[5];
 	while(scanf("%d,%d,%d,%d,%d",&cards[0],&cards[1],&cards[2],&cards[3],&cards[4])!=EOF){
 		int count[14]={0};
 		for(int i=0;i<5;i++)count[cards[i]]++;
  		yakuPrint(cards,count);
 	}
 }




*問39　Roman Figure
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0039
ローマ数字を１０進数になおす問題。
大きな数小さな数大きな数と続いた場合のルールが書いてないがそういう場合はたぶんルール違反なのだろう。
再帰下降構文解析で構文ルールでチェックするのかな。

 #include<stdio.h>
 #include<map>
 int main(){
 	char roman[102];
 	std::map<char,int> toNum;
 	toNum['I']=1;
 	toNum['V']=5;
 	toNum['X']=10;
 	toNum['L']=50;
 	toNum['C']=100;
  	toNum['D']=500;
	toNum['M']=1000;
 	toNum['\0']=-1;
 	while(scanf("%s",roman)!=EOF){
  		int ans=0;
 		int Reserve=0;
 		int num1,num2;
 		for(int i=0;roman[i]!='\0';i++){
 			num1=toNum[roman[i]];
 			num2=toNum[roman[i+1]];
 			if(num1>num2){
  				ans+=Reserve+num1;
 				Reserve=0;
 			}else if(num1==num2){
 				Reserve+=num1;
 			}else if(num1<num2){
  				ans-=(Reserve+num1);
 				Reserve=0;
 			}
 		}
  		printf("%d\n",ans);
 	}
 }





*Affine Cipher
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0040
とりあえず全探索しても計算量が変わらないので全探索。
上位の人はすごい解き方をしてるのだろうか？


 #include<stdio.h>
 #include<string.h>
 #include <ctype.h>
 
 char toChange(char c,int a,int b){
 	if(islower(c))return (a*(c-'a')+b)%26+'a';
 	return c;
 }
  
 int main(){
 	//thatとthisを変換したものと照合したほうが速いけれど計算量的に大差ないので
 	//記述の簡易さを優先
  	char text[256],change[256],c;
	char THIS[6]="this";
  	char THAT[6]="that";
 	char *ret;
 	int n;
 	scanf("%d%*c",&n);
 	while(n--){
 		bool hit=false;
 		scanf("%[^\n]%*c",text);
 		int a,b;
 		for(a=0;a<=26;a++){
 			for(b=0;b<=26;b++){
 				int p=-1;
 				do{
  					p++;
 					change[p]=toChange(text[p],a,b);
 				}while(change[p]!='\0');
 				
 				ret=change;
 				while((ret=strstr(ret,THIS))!=NULL){
 					if(ret[4]=='\0'||ret[4]==' '){
 						hit=true;
 						break;
 					}
 					ret++;
 				}
  				ret=change;
 				while((ret=strstr(ret,THAT))!=NULL){
 					if(ret[4]=='\0'||ret[4]==' '){
 						hit=true;
 						break;
 					}
 					ret++;
 				}
 				if(hit==true)break;
  			}
 			if(hit==true)break;
 		}
  		printf("%s\n",change);
 	}
 }

*問３６ A Figure on Surface
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0036
おかれたブロックを判定する問題。
解法
ブロックの一番上で一番左のブロックを基準に、その右3マス下３マスのブロックの状態をビットにして判断します。
解いたのでほかの人のコードも見ましたが私は平均的なコードでした。
コードの短さ一位のコードはもはや異次元、数学みたいなコードでなにがなにやら？
MOD演算の概念を使ってる雰囲気だけど読み解けなかった。
自分がホビーアルゴリズマーとして３流なんだなと感じるしだい。

 #include<stdio.h>
 #include<string.h>
 
 char blockType(char test[12][12],int r,int c){
 	int pow2=1,sum=0;
 	for(int i=0;i<3;i++){
 		for(int j=0;j<3;j++){
 			if(test[r+i][c+j]=='1'){
 				sum+=pow2;
 			}
 			pow2*=2;
 		}
 	}
 	char re;
 	if(sum==27)re='A';
 	if(sum==73)re='B';
 	if(sum==7)re='C';
 	if(sum==9)re='D';
 	if(sum==51)re='E';
 	if(sum==153)re='F';
 	if(sum==11)re='G';
 	return re;
 }
 
 int main(){
 	char board[12][12];
 	int r,c;
  	memset(board,0,sizeof(board));
 	while(1){
 		r=c=-1;
 		if(scanf("%s",board[0])==EOF)break;
 		for(int i=1;i<8;i++){
 			scanf("%s",board[i]);
  			for(int j=8;j<12;j++)board[i][j]='\0';
 		}
 		
 		for(int i=0;i<8;i++){
 			for(int j=0;j<8;j++){
  				if(r==-1&&board[i][j]=='1'){
 					r=i;
 					c=j;
 				}
  			}
 		}
 		printf("%c\n",blockType(board,r,c));
 	}
 } 




*問37　Path on a Grid
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0037
壁に右手をついて歩く人の移動を表示する問題。


解法
一見混乱する問題ですが
右手を常につけているのですから。
西を向いているときは必ず北の壁に手をつけ
東を向いているときは必ず南の壁に手を付けています。
曲がる方向は東向きの移動なら、北　東　南　それと西にもどる　　の順でその方向へ向かう壁がないか検証します。
他の方向も回転しただけで検証順序が同じです。
次の位置決めに不要な情報を全部取り去るとコードが簡素になります。

moveCommit関数を配列にすればもう少し抽象化できるかもしれません。

 #include<stdio.h>
 #include<string.h>
 const int Right=0;
 const int Up=1;
 const int Left=2;
 const int Down=3;
 int moves[4][4]={{Up,Right,Down,Left},
 		 {Left,Up,Right,Down},
 		 {Down,Left,Up,Right},
 		 {Right,Down,Left,Up}};
 char walls[100][100];
 int height=0;
 
 bool is_wall(int x,int y){
 	if(y<0||height<=y)return false;
 	if(x<0||strlen(walls[y])<=x)return false;
 	if(walls[y][x]!='1')return false;
 	return true;
 }
 
 void moveCommit(int x,int y,int r,int &nx,int &ny,int &nr){
 	for(int i=0;i<4;i++){
 		int r1=moves[r][i];
		if(r1==Up){
 			int py=y*2-1;
 			int px=x;
 			if(is_wall(px,py)){
 				nx=x;
 				ny=y-1;
 				nr=Up;
 				return ;
 			}
 		}else if(r1==Right){
 			int py=y*2;
 			int px=x;
  			if(is_wall(px,py)){
 				nx=x+1;
 				ny=y;
 				nr=Right;
 				return;
 			}
 		}else if(r1==Left){
 			int py=y*2;
 			int px=x-1;
 			if(is_wall(px,py)){
 				nx=x-1;
  				ny=y;
 				nr=Left;
 				return;
 			}
 		}else if(r1==Down){
 			int py=y*2+1;
 			int px=x;
 			if(is_wall(px,py)){
 				nx=x;
  				ny=y+1;
 				nr=Down;
 				return;
 			}
 		}
 	}
 }
 
 int main(){
 	int nowX=1,nowY=0,nowR=0,nextX,nextY,nextR;
 	char muki[5]="RULD";
  	
 	for(height=0;scanf("%s",walls[height])!=EOF;height++);
 	printf("R");
 	while(nowX!=0||nowY!=0){
 		moveCommit(nowX,nowY,nowR,nextX,nextY,nextR);
 		printf("%c",muki[nextR]);
 		nowX=nextX;
  		nowY=nextY;
 		nowR=nextR;
 	}
  	printf("\n");
 }




*問38Poker Hand
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0038
簡易ルールのポーカーの役を判定する問題。
解法
yakuPrint1で同じ数字のチェック。
yakuPrint2でストレートのチェック。
それだけ。

 #include<stdio.h>
 #include<algorithm>
 #include <functional>
 
 bool yakuPrint1(int count[14]){
 	std::sort(count,count+14,std::greater<int>());
 	bool printOK=true;
 	if(count[0]==4){
 		printf("four card\n");
 	}else if(count[0]==3&&count[1]==2){
 		printf("full house\n");
 	}else if(count[0]==3){
 		printf("three card\n");
 	}else if(count[0]==2&&count[1]==2){
 		printf("two pair\n");
 	}else if(count[0]==2){
 		printf("one pair\n");
  	}else{
 		printOK=false;
 	}
 	return printOK;
 } 
 bool yakuPrint2(int cards[5]){
 	std::sort(cards,cards+5);
 	bool printOK=true;
 	for(int i=1;i<5;i++){
 		if(cards[i-1]+1!=cards[i])printOK=false;
 	}
 	if(printOK==true){
  		printf("straight\n");
 	}else{
 		if(cards[0]==1&&cards[1]==10&&cards[2]==11&&cards[3]==12&&cards[4]==13){
 			printf("straight\n");
 			printOK=true;
  		}
 	}
 	return printOK;
 }
 
 void yakuPrint(int cards[5],int count[14]){
  	if(yakuPrint1(count)||yakuPrint2(cards)){
 		//何もなし
 	}else{
 		printf("null\n");
  	}
 }
 
 int main(){
  	int cards[5];
 	while(scanf("%d,%d,%d,%d,%d",&cards[0],&cards[1],&cards[2],&cards[3],&cards[4])!=EOF){
 		int count[14]={0};
 		for(int i=0;i<5;i++)count[cards[i]]++;
  		yakuPrint(cards,count);
 	}
 }




*問39　Roman Figure
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0039
ローマ数字を１０進数になおす問題。
大きな数小さな数大きな数と続いた場合のルールが書いてないがそういう場合はたぶんルール違反なのだろう。
再帰下降構文解析で構文ルールでチェックするのかな。

 #include<stdio.h>
 #include<map>
 int main(){
 	char roman[102];
 	std::map<char,int> toNum;
 	toNum['I']=1;
 	toNum['V']=5;
 	toNum['X']=10;
 	toNum['L']=50;
 	toNum['C']=100;
  	toNum['D']=500;
	toNum['M']=1000;
 	toNum['\0']=-1;
 	while(scanf("%s",roman)!=EOF){
  		int ans=0;
 		int Reserve=0;
 		int num1,num2;
 		for(int i=0;roman[i]!='\0';i++){
 			num1=toNum[roman[i]];
 			num2=toNum[roman[i+1]];
 			if(num1>num2){
  				ans+=Reserve+num1;
 				Reserve=0;
 			}else if(num1==num2){
 				Reserve+=num1;
 			}else if(num1<num2){
  				ans-=(Reserve+num1);
 				Reserve=0;
 			}
 		}
  		printf("%d\n",ans);
 	}
 }





*Affine Cipher
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0040
とりあえず全探索しても計算量が変わらないので全探索。
上位の人はすごい解き方をしてるのだろうか？


 #include<stdio.h>
 #include<string.h>
 #include <ctype.h>
 
 char toChange(char c,int a,int b){
 	if(islower(c))return (a*(c-'a')+b)%26+'a';
 	return c;
 }
  
 int main(){
 	//thatとthisを変換したものと照合したほうが速いけれど計算量的に大差ないので
 	//記述の簡易さを優先
  	char text[256],change[256],c;
	char THIS[6]="this";
  	char THAT[6]="that";
 	char *ret;
 	int n;
 	scanf("%d%*c",&n);
 	while(n--){
 		bool hit=false;
 		scanf("%[^\n]%*c",text);
 		int a,b;
 		for(a=0;a<=26;a++){
 			for(b=0;b<=26;b++){
 				int p=-1;
 				do{
  					p++;
 					change[p]=toChange(text[p],a,b);
 				}while(change[p]!='\0');
 				
 				ret=change;
 				while((ret=strstr(ret,THIS))!=NULL){
 					if(ret[4]=='\0'||ret[4]==' '){
 						hit=true;
 						break;
 					}
 					ret++;
 				}
  				ret=change;
 				while((ret=strstr(ret,THAT))!=NULL){
 					if(ret[4]=='\0'||ret[4]==' '){
 						hit=true;
 						break;
 					}
 					ret++;
 				}
 				if(hit==true)break;
  			}
 			if(hit==true)break;
 		}
  		printf("%s\n",change);
 	}
 }