会津大学オンラインジャッジを解くページ。 *問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> 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); if(scanf("%c",&nowP)==EOF)break; } }