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

AOJ再挑戦66~70 - (2014/01/31 (金) 07:40:48) の1つ前との変更点

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

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

 会津大学オンラインジャッジを解くページ。
 
 *問66 Tic Tac Toe
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0066
 チックタックトゥの勝敗判定をする問題。
 
 自分で考えられる限りの短縮を図ったものの平凡なショートコーディングになった。
 この問題昔掲示板でヒントはもらって書いたのだけど、今回はその時より短くなっている。
 短さ1位の人のコードは想像もつかないがAOJの外には1位の人より上がいるのがネットの世界。
 すごいと思う。
 AOJばっかりに閉じこもってないで少しは外に出ないとダメか。
 コードの短さ6/542位うーん平凡。
 
 
  #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(列数*行数)です。
 再帰を使った解法だと末尾最適化に成功しない限り、関数の再帰呼び出しが深くなりすぎてエラーを起こすでしょう。
 
 
 
  #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));
 			}
  		}
-  		printf("%d\n",spentsNo.size()-1+ansAdd);
+  		std::cout<<spentsNo.size()-1+ansAdd<<"\n";
  		if(scanf("%c",&nowP)==EOF)break;
  	}
  }