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

「AOJ再挑戦66～70」(2014/02/02 (日) 14:48:32) の最新版変更点

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

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

会津大学オンラインジャッジを解くページ。

*問66　Tic Tac Toe
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0066
チックタックトゥの勝敗判定をする問題。

自分で考えられる限りの短縮を図ったものの平凡なショートコーディングになった。
この問題昔掲示板でヒントはもらって書いたのだけど、今回はその時より短くなっている。
短さ１位の人のコードは想像もつかないがAOJの外には１位の人より上がいるのがネットの世界。
すごいと思う。
AOJばっかりに閉じこもってないで少しは外に出ないとダメか。
コードの短さ6/542位うーん平凡。

コード解説
rはマトリックスです。
ｂに盤面データが保存されています、マス目に番号を付けると。
012
345
678

となったらチェックすべきは
012
345
678
036
147
258
048
246
の8通り。
全部　ｐ、ｐ+ｄ、ｐ+２ｄと表せます。
そして(チェックすべき３マスに入ってる文字のビットOr)に18でマスクをとると。
ooo＝2
か
xxx＝16
それ以外は全部18になります。
％３をとれば、ｘｘｘなら1、oooなら２、それ以外なら0を返す検出器が作れます。
あとは0を入れたｔと8か所のbitORをとるだけです。



 #include<stdio.h>
 int main(){
 	char *r="0001223613432311",b[10],i,t,p,d;
  	while(scanf("%s",b)>0){
 		t=i=0;
 		while(i<8){
 			d=r[i+8]%8;
 			p=r[i++]%8;
  			t|=((b[p]|b[p+d]|b[p+d*2])&18)%3;			
 		}
 		printf("%c\n","dxo"[t]);
  	}
 }



*問67 The Number of Island
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0067
格子上のデータで海と陸があらわされている島の数を数えよという問題。
解法
この問題12*1２で標準出力から読み込む問題ですが。
島と海のデータがテキストファイルで与えられデータが大きくなった場合。
たとえば数十万行*数十万列のデータでも計算できるようなアルゴリズムを構築しました。
計算量はBigO(列数*行数*log(列数,2))です。
再帰を使った解法だと末尾最適化に成功しない限り、関数の再帰呼び出しが深くなりすぎてエラーを起こすでしょう。



 #include<stdio.h>
 #include<set>
 #include<iostream>
 const int SIZE=12;
 int main(){
 	char nowP;
 	while(1){
  		std::set<long long int> spentsNo;
 		std::set<long long int>::reverse_iterator rIt;
 		spentsNo.insert(0);
 		long long int ansAdd=0;
 		long long int oldRowMemo[SIZE]={0};
 		for(int r=0;r<SIZE;r++){
 			long long int nowRowMemo[SIZE]={0};
 			for(int c=0;c<SIZE;c++){
 				scanf("%c",&nowP);
 				if(nowP=='0'){
 					oldRowMemo[c]=nowRowMemo[c]=0;
 					continue;
 				}
 				long long int max=0;
 				if(0<c){
 					max=nowRowMemo[c-1];	
 				}
  				if(0<r){
 					max=max>oldRowMemo[c]?max:oldRowMemo[c];
 				}
 				if(max==0){
 					rIt=spentsNo.rbegin();
 					max=(*rIt)+1;
 					spentsNo.insert(max);
 				}
 				nowRowMemo[c]=max;
 				long long int t=nowRowMemo[c-1];
  				if(0<c&&t>0&&t<max){
 					spentsNo.erase(t);
 				}
 				t=oldRowMemo[c];
 				if(0<r&&t>0&&t<max){
 					spentsNo.erase(t);
 				}
 				oldRowMemo[c]=max;
 			}
 			scanf("%c",&nowP);//改行読み込み
 			//いらないデータの掃除
 			std::set<long long int> nowRowSet,dellNo;
 			for(int i=0;i<SIZE;i++){
 				nowRowSet.insert(nowRowMemo[i]);
 			}
 			for(rIt=spentsNo.rbegin();rIt!=spentsNo.rend();rIt++){
 				if(nowRowSet.find((*rIt))==nowRowSet.end()&&(*rIt)>0){
  					dellNo.insert((*rIt));
 				}
 			}
 			ansAdd+=dellNo.size();
 			for(rIt=dellNo.rbegin();rIt!=dellNo.rend();rIt++){
 				spentsNo.erase((*rIt));
			}
 		}
  		std::cout<<spentsNo.size()-1+ansAdd<<"\n";
 		if(scanf("%c",&nowP)==EOF)break;
 	}
 }

*68　Enclose Pins with a Rubber Band
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0068
与えられた平面上の点を結んで全部の点を囲む凸多角形を作るとき、凸多角形に使われない天の数を答えよ
という問題。
解法
一番下の一番左の点Aから初めて最初は1,0のなす角が一番小さい点を凸多角形の2つ目の点Bとし、3つ目の点はベクトルABとベクトルBCのなす角が一番小さな点を3つ目の点としてあとはこのループで点Aに戻ってくるまで続ける。


 #include<stdio.h>
 #include<math.h>
 double calcCos(double x0,double y0,double x1,double y1,double dx0,double dy0){
 	double dx1=x1-x0;
 	double dy1=y1-y0;
 	double len0=hypot(dx0,dy0);
 	double len1=hypot(dx1,dy1);
  	double naiseki=dx0*dx1+dy0*dy1;
 	return naiseki/(len0*len1);
 }
 
 void calc(int n){
 	double xs[101],ys[101],downY=1001,leftX=1001,oldDx=1,oldDy=0;
 	int nowP,oldP,startP,count=0;
 	//問題で言及されてる内容からいろいろ手抜き処理で記述
  	//言及がなければ無限ループになる可能性あり
 
 	for(int i=0;i<n;i++){
 		scanf("%lf,%lf",&xs[i],&ys[i]);
 		if((ys[i]<downY)||(ys[i]==downY&&xs[i]<leftX)){
 			downY=ys[i];
 			leftX=xs[i];
 			startP=oldP=i;
   		}
  	}
 	while(count<2||nowP!=startP){
 		double cosMax=-1,cosTemp;
  		for(int i=0;i<n;i++){
 			if(i==oldP)continue;
  			cosTemp=calcCos(xs[oldP],ys[oldP],xs[i],ys[i],oldDx,oldDy);
 			if(cosTemp>cosMax){
 				nowP=i;
 				cosMax=cosTemp;
 			}
 		}
 		oldDx=xs[nowP]-xs[oldP];
 		oldDy=ys[nowP]-ys[oldP];
 		oldP=nowP;
 		count++;
 		
 	}
 	printf("%d\n",n-count);
 }
 
 int main(){
 	int n;
  	while(scanf("%d",&n)!=EOF){
 		if(n==0)break;
 		calc(n);
 	}
 }






*問69　Drawing Lots II
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0069
あみだくじを題材にした問題。

各場所に一本だけ線を足した場合を各々でシミュレーションするのがコードも短くなってよいのですが。
数万列*数万行になっても定数を変えるだけでBigO（列数*行数）で計算が終わるように記述してみました。
一本線を足す場合だとBigO(行数＾２*列数)となります。

 #include<stdio.h>
 #include<string.h>
 #include<algorithm>
 
 struct S{
 	int row,col,hit;
 	bool operator<(const S& s)const{
 		if(hit!=s.hit)return hit>s.hit;
 		return row<s.row;
 	}
 };
 
 S minS(const S& s1,const S& s2){
 	return s2<s1?s2:s1;
 }
 
 void search(int n){
 	int m,atari,d;
 	char row[12];
 	scanf("%d %d %d",&m,&atari,&d);
	S s,memo[2][12];
 	s.hit=0;
 	s.row=d+1;
 	for(int i=1;i<=n;i++){
 		s.hit=(i==m);
 		memo[0][i]=s;
 		s.hit=0;
  		memo[1][i]=s;
	}
 	
  	for(int i=0;i<d;i++){
 		scanf("%s",&row[1]);
		row[0]=row[n]='0';
  		for(int col=1;col<n;col++){
 			//横線を引かない
 			if(row[col]=='1'){
 				std::swap(memo[0][col],memo[0][col+1]);
 				std::swap(memo[1][col],memo[1][col+1]);
 			}
 			//横線を引けた
 			if(row[col-1]=='0'&&row[col]=='0'&&row[col+1]=='0'){
 				s=memo[0][col];
  				s.row=i+1;
 				s.col=col;
 				memo[1][col+1]=minS(s,memo[1][col+1]);
 				s=memo[0][col+1];
 				s.row=i+1;
 				s.col=col;
  				memo[1][col]  =minS(s,memo[1][col]);
 			}
 		}
 		
  	}
 	if(memo[0][atari].hit==1){
 		printf("0\n");
 	}else if(memo[1][atari].hit==1){
 		s=memo[1][atari];
 		printf("%d %d\n",s.row,s.col);
  	}else{
 		printf("1\n");
 	}
 } 
 
 int main(){
 	int n;
  	while(scanf("%d",&n)!=EOF){
 		if(n==0)break;
  		search(n);
 	}
 }

会津大学オンラインジャッジを解くページ。

*問66　Tic Tac Toe
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0066
チックタックトゥの勝敗判定をする問題。

自分で考えられる限りの短縮を図ったものの平凡なショートコーディングになった。
この問題昔掲示板でヒントはもらって書いたのだけど、今回はその時より短くなっている。
短さ１位の人のコードは想像もつかないがAOJの外には１位の人より上がいるのがネットの世界。
すごいと思う。
AOJばっかりに閉じこもってないで少しは外に出ないとダメか。
コードの短さ6/542位うーん平凡。

コード解説
rはマトリックスです。
ｂに盤面データが保存されています、マス目に番号を付けると。
012
345
678

となったらチェックすべきは
012
345
678
036
147
258
048
246
の8通り。
全部　ｐ、ｐ+ｄ、ｐ+２ｄと表せます。
そして(チェックすべき３マスに入ってる文字のビットOr)に18でマスクをとると。
ooo＝2
か
xxx＝16
それ以外は全部18になります。
％３をとれば、ｘｘｘなら1、oooなら２、それ以外なら0を返す検出器が作れます。
あとは0を入れたｔと8か所のbitORをとるだけです。



 #include<stdio.h>
 int main(){
 	char *r="0001223613432311",b[10],i,t,p,d;
  	while(scanf("%s",b)>0){
 		t=i=0;
 		while(i<8){
 			d=r[i+8]%8;
 			p=r[i++]%8;
  			t|=((b[p]|b[p+d]|b[p+d*2])&18)%3;			
 		}
 		printf("%c\n","dxo"[t]);
  	}
 }



*問67 The Number of Island
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0067
格子上のデータで海と陸があらわされている島の数を数えよという問題。
解法
この問題12*1２で標準出力から読み込む問題ですが。
島と海のデータがテキストファイルで与えられデータが大きくなった場合。
たとえば数十万行*数十万列のデータでも計算できるようなアルゴリズムを構築しました。
計算量はBigO(列数*行数*log(列数,2))です。
再帰を使った解法だと末尾最適化に成功しない限り、関数の再帰呼び出しが深くなりすぎてエラーを起こすでしょう。



 #include<stdio.h>
 #include<set>
 #include<iostream>
 const int SIZE=12;
 int main(){
 	char nowP;
 	while(1){
  		std::set<long long int> spentsNo;
 		std::set<long long int>::reverse_iterator rIt;
 		spentsNo.insert(0);
 		long long int ansAdd=0;
 		long long int oldRowMemo[SIZE]={0};
 		for(int r=0;r<SIZE;r++){
 			long long int nowRowMemo[SIZE]={0};
 			for(int c=0;c<SIZE;c++){
 				scanf("%c",&nowP);
 				if(nowP=='0'){
 					oldRowMemo[c]=nowRowMemo[c]=0;
 					continue;
 				}
 				long long int max=0;
 				if(0<c){
 					max=nowRowMemo[c-1];	
 				}
  				if(0<r){
 					max=max>oldRowMemo[c]?max:oldRowMemo[c];
 				}
 				if(max==0){
 					rIt=spentsNo.rbegin();
 					max=(*rIt)+1;
 					spentsNo.insert(max);
 				}
 				nowRowMemo[c]=max;
 				long long int t=nowRowMemo[c-1];
  				if(0<c&&t>0&&t<max){
 					spentsNo.erase(t);
 				}
 				t=oldRowMemo[c];
 				if(0<r&&t>0&&t<max){
 					spentsNo.erase(t);
 				}
 				oldRowMemo[c]=max;
 			}
 			scanf("%c",&nowP);//改行読み込み
 			//いらないデータの掃除
 			std::set<long long int> nowRowSet,dellNo;
 			for(int i=0;i<SIZE;i++){
 				nowRowSet.insert(nowRowMemo[i]);
 			}
 			for(rIt=spentsNo.rbegin();rIt!=spentsNo.rend();rIt++){
 				if(nowRowSet.find((*rIt))==nowRowSet.end()&&(*rIt)>0){
  					dellNo.insert((*rIt));
 				}
 			}
 			ansAdd+=dellNo.size();
 			for(rIt=dellNo.rbegin();rIt!=dellNo.rend();rIt++){
 				spentsNo.erase((*rIt));
			}
 		}
  		std::cout<<spentsNo.size()-1+ansAdd<<"\n";
 		if(scanf("%c",&nowP)==EOF)break;
 	}
 }

*68　Enclose Pins with a Rubber Band
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0068
与えられた平面上の点を結んで全部の点を囲む凸多角形を作るとき、凸多角形に使われない天の数を答えよ
という問題。
解法
一番下の一番左の点Aから初めて最初は1,0のなす角が一番小さい点を凸多角形の2つ目の点Bとし、3つ目の点はベクトルABとベクトルBCのなす角が一番小さな点を3つ目の点としてあとはこのループで点Aに戻ってくるまで続ける。


 #include<stdio.h>
 #include<math.h>
 double calcCos(double x0,double y0,double x1,double y1,double dx0,double dy0){
 	double dx1=x1-x0;
 	double dy1=y1-y0;
 	double len0=hypot(dx0,dy0);
 	double len1=hypot(dx1,dy1);
  	double naiseki=dx0*dx1+dy0*dy1;
 	return naiseki/(len0*len1);
 }
 
 void calc(int n){
 	double xs[101],ys[101],downY=1001,leftX=1001,oldDx=1,oldDy=0;
 	int nowP,oldP,startP,count=0;
 	//問題で言及されてる内容からいろいろ手抜き処理で記述
  	//言及がなければ無限ループになる可能性あり
 
 	for(int i=0;i<n;i++){
 		scanf("%lf,%lf",&xs[i],&ys[i]);
 		if((ys[i]<downY)||(ys[i]==downY&&xs[i]<leftX)){
 			downY=ys[i];
 			leftX=xs[i];
 			startP=oldP=i;
   		}
  	}
 	while(count<2||nowP!=startP){
 		double cosMax=-1,cosTemp;
  		for(int i=0;i<n;i++){
 			if(i==oldP)continue;
  			cosTemp=calcCos(xs[oldP],ys[oldP],xs[i],ys[i],oldDx,oldDy);
 			if(cosTemp>cosMax){
 				nowP=i;
 				cosMax=cosTemp;
 			}
 		}
 		oldDx=xs[nowP]-xs[oldP];
 		oldDy=ys[nowP]-ys[oldP];
 		oldP=nowP;
 		count++;
 		
 	}
 	printf("%d\n",n-count);
 }
 
 int main(){
 	int n;
  	while(scanf("%d",&n)!=EOF){
 		if(n==0)break;
 		calc(n);
 	}
 }






*問69　Drawing Lots II
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0069
あみだくじを題材にした問題。

各場所に一本だけ線を足した場合を各々でシミュレーションするのがコードも短くなってよいのですが。
数万列*数万行になっても定数を変えるだけでBigO（列数*行数）で計算が終わるように記述してみました。
一本線を足す場合だとBigO(行数＾２*列数)となります。

 #include<stdio.h>
 #include<string.h>
 #include<algorithm>
 
 struct S{
 	int row,col,hit;
 	bool operator<(const S& s)const{
 		if(hit!=s.hit)return hit>s.hit;
 		return row<s.row;
 	}
 };
 
 S minS(const S& s1,const S& s2){
 	return s2<s1?s2:s1;
 }
 
 void search(int n){
 	int m,atari,d;
 	char row[12];
 	scanf("%d %d %d",&m,&atari,&d);
	S s,memo[2][12];
 	s.hit=0;
 	s.row=d+1;
 	for(int i=1;i<=n;i++){
 		s.hit=(i==m);
 		memo[0][i]=s;
 		s.hit=0;
  		memo[1][i]=s;
	}
 	
  	for(int i=0;i<d;i++){
 		scanf("%s",&row[1]);
		row[0]=row[n]='0';
  		for(int col=1;col<n;col++){
 			//横線を引かない
 			if(row[col]=='1'){
 				std::swap(memo[0][col],memo[0][col+1]);
 				std::swap(memo[1][col],memo[1][col+1]);
 			}
 			//横線を引けた
 			if(row[col-1]=='0'&&row[col]=='0'&&row[col+1]=='0'){
 				s=memo[0][col];
  				s.row=i+1;
 				s.col=col;
 				memo[1][col+1]=minS(s,memo[1][col+1]);
 				s=memo[0][col+1];
 				s.row=i+1;
 				s.col=col;
  				memo[1][col]  =minS(s,memo[1][col]);
 			}
 		}
 		
  	}
 	if(memo[0][atari].hit==1){
 		printf("0\n");
 	}else if(memo[1][atari].hit==1){
 		s=memo[1][atari];
 		printf("%d %d\n",s.row,s.col);
  	}else{
 		printf("1\n");
 	}
 } 
 
 int main(){
 	int n;
  	while(scanf("%d",&n)!=EOF){
 		if(n==0)break;
  		search(n);
 	}
 }




*Combination of Number Sequences
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0070
0～9までの10個の数をｎ個使ってK1+２*K2+,,,n*Kn＝ｓを作る作り方は何通りあるか？

解法
平凡な動的計画法でテーブル化して解きました。


 #include<stdio.h>
 #include<string.h>
 const int MAX=330;
 const int BIT_LIMIT=1024;
 int memo[2][BIT_LIMIT][MAX+1],ans[11][MAX+1];
 int main(){
     
    memset(memo,0,sizeof(memo));
    memo[0][0][0]=1;
    memset(ans,0,sizeof(ans));
    for(int i=1;i<=10;i++){
        int now =(i+1)%2;
        int next=i%2;
        for(int j=0;j<BIT_LIMIT;j++){
            for(int k=0;k<=9;k++){
                int b=1<<k;
                if((b&j)>0)continue;
                for(int l=0;l<=MAX-k*i;l++){
                    memo[next][j|b][l+k*i]+=memo[now][j][l];
                }
            }
        }
        for(int j=0;j<BIT_LIMIT;j++){
            for(int l=0;l<=MAX;l++){
                ans[i][l]+=memo[next][j][l];
            }
        }
        memset(memo[now],0,sizeof(memo[now]));
    }
    int n,s;
    while(scanf("%d %d",&n,&s)!=EOF){
        if(n>10 || s>MAX){
            printf("0\n");
        }else{
             
             printf("%d\n",ans[n][s]);
        }
     }
 }