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

AOJ再挑戦66~70 - (2014/02/02 (日) 13:48:50) の最新版との変更点

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

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

 会津大学オンラインジャッジを解くページ。
 
 *問66 Tic Tac Toe
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0066
 チックタックトゥの勝敗判定をする問題。
 
 自分で考えられる限りの短縮を図ったものの平凡なショートコーディングになった。
 この問題昔掲示板でヒントはもらって書いたのだけど、今回はその時より短くなっている。
 短さ1位の人のコードは想像もつかないがAOJの外には1位の人より上がいるのがネットの世界。
 すごいと思う。
 AOJばっかりに閉じこもってないで少しは外に出ないとダメか。
 コードの短さ6/542位うーん平凡。
 
 コード解説
 rはマトリックスです。
 bに盤面データが保存されています、マス目に番号を付けると。
 012
 345
 678
 
 となったらチェックすべきは
 012
 345
 678
 036
 147
 258
 048
 246
 の8通り。
 全部 p、p+d、p+2dと表せます。
 そして(チェックすべき3マスに入ってる文字のビットOr)に18でマスクをとると。
 ooo=2
 か
 xxx=16
 それ以外は全部18になります。
 %3をとれば、xxxなら1、oooなら2、それ以外なら0を返す検出器が作れます。
 あとは0を入れたtと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*12で標準出力から読み込む問題ですが。
 島と海のデータがテキストファイルで与えられデータが大きくなった場合。
 たとえば数十万行*数十万列のデータでも計算できるようなアルゴリズムを構築しました。
-計算量はBigO(列数*行数*log(列数,10))です。
+計算量は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);
  	}
  }
 
 
 
 
 
 
-*Drawing Lots II
+*問69 Drawing Lots II
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0069
-一本線を足した場合を各々でシミュレーションするのがコードも短くなってよいのですが。
-数万列*数万行になっても定数を変えるだけでBigO(列数*行数)で計算が終わるように記述してみました。
+あみだくじを題材にした問題。
 
+各場所に一本だけ線を足した場合を各々でシミュレーションするのがコードも短くなってよいのですが。
+数万列*数万行になっても定数を変えるだけでBigO(列数*行数)で計算が終わるように記述してみました。
+一本線を足す場合だとBigO(行数^2*列数)となります。
 
  #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個の数をn個使ってK1+2*K2+,,,n*Kn=sを作る作り方は何通りあるか?
+
+解法
+平凡な動的計画法でテーブル化して解きました。
+
+
+ #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]);
+        }
+     }
  }