「AOJ再挑戦66～70」の編集履歴（バックアップ）一覧に戻る

AOJ再挑戦66～70 - (2014/02/02 (日) 12:01:49) の編集履歴(バックアップ)

---

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

問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を入れたｔとビットor8か所のチェックでとるだけです。

#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(列数*行数)です。
再帰を使った解法だと末尾最適化に成功しない限り、関数の再帰呼び出しが深くなりすぎてエラーを起こすでしょう。

#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);
	}
}