「AOJ61～70」の編集履歴（バックアップ）一覧はこちら

「AOJ61～70」(2011/08/22 (月) 11:39:10) の最新版変更点

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

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

*0061　Rank Checker
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0061
パソコン甲子園の参加チームの整理番号と得点が与えられます。
どのチームが何位だったか問われるので順位を表示するという問題です。

チームデータをベクターに確保し得点順にソートします。
これを上位から読み上位チームの番号と順位の組をＭａｐに保存します。
も少し賢い方法があるような気もしますが標準的に実装してみました。
これくらいならＥＸＣＥＬで計算した方が早そうです。


 #include<stdio.h>
 #include<vector>
 #include<map>
 #include <algorithm>
 struct team{
	int no,p;
	bool operator<(const team t)const {
		return p>t.p;
	}
 };
 int main(){
	std::vector<team> teams;
	team t;
	do{
		scanf("%d,%d",&t.no,&t.p);
		teams.push_back(t);
	}while(t.no!=0 && t.p!=0);
	std::sort(teams.begin(),teams.end());
	std::vector<team>::iterator it=teams.begin();
	int rank=1,p=(*it).p;
	std::map<int,int> memo;
	while(it!=teams.end()){
		if(p==(*it).p){
			memo[(*it).no]=rank;
		}else{
			p=(*it).p;
			rank++;
			memo[(*it).no]=rank;
		}
		it++;
	}
	while(scanf("%d",&p)!=EOF){
		printf("%d\n",memo[p]);
	}
 }





----
*0062 What is the Bottommost?
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0062
逆パスカルの三角形です。
一段ずつ足し算して最下段の数字を求めよという問題です。
解法
何列めの数字が最下段に行くまでに何回足されるかを計算するとcomになるという性質を利用します。

 #include<stdio.h>
 int main(){
	char t[11];
	int sum,com[]={1,10,45,120,210};
	while(scanf("%s",t)!=EOF){
		sum=0;
		for(int i=0;i<5;i++) sum+=com[i]*(t[i]+t[9-i]-96);
		printf("%d\n",sum%10);
	}
 }




----
*0063　Palindrome
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0063
普通にアセプト。
stdには、配列をリバースするメソッドがあるのでそれを使うともっと簡単になるらしい。

 #include<stdio.h>
 #include<string.h>
 int main(){
	char text[101];
	bool ok;
	int len,ans=0;
	while(scanf("%s",text)!=EOF){
		ok=true;
		len=strlen(text);
		for(int i=0;i<len/2;i++){
			if(text[i]!=text[len-i-1]){
				ok=false;
				break;
			}
		}
		ans+=ok?1:0;
	}
	printf("%d\n",ans);
 }





----
*0064　Secret Number
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0064
状態遷移マシンを作って簡単にアセプト。
一行ずつでなく一文字ずつ読み込めばもっとコードがシンプルになるようだ。
状態遷移マシンとしてみた場合一番簡単な部類に入ると思う。


 #include<stdio.h>
 #include<string.h>
 int main(){
	char t[81];
	int len,mod,sum=0,ans=0;
	while(scanf("%s",t)!=EOF){
		len=strlen(t);
		mod=0;
		sum=0;
		for(int i=0;i<len;i++){
			if('0'<=t[i] && t[i]<='9'){
				sum*=10;
				sum+=t[i]-'0';
			}else{
				ans+=sum;
				sum=0;
			}
		}
		ans+=sum;
	}
	printf("%d\n",ans);
 }





----
*0065　Trading
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0065
今月の取引と先月の取引を別々にカウント。
月データが複数になった場合はvector<map<int,int>>のようなコードが必要になる？
愚直に実装したがもう少し簡単なコードになるような気もする。

 #include<stdio.h>
 #include<map>
 int main(){
	int no,day;
	char re[3];
	std::map<int,int> now,old;
	
	while(1){
		scanf("%d,%d",&no,&day);
		if(now.find(no)==now.end()){
			now[no]=1;
		}else{
			now[no]++;
		}
		scanf("%[\n]",re);
		if(re[1]!='\0') break;
	}
	while(scanf("%d,%d",&no,&day)!=EOF){
		if(old.find(no)==old.end()){
			old[no]=1;
		}else{
			old[no]++;
		}
	}
	std::map<int,int>::iterator it=old.begin();
	while(it!=old.end()){
		if(now.find((*it).first)!=now.end()){
			printf("%d %d\n",(*it).first,(*it).second+now[(*it).first]);
		}
		it++;
	}
 }






----
*0066 Tic Tac Toe
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0066
コードの半分は掲示板で質問して短くしてもらいました。
半分は自分で短くしました。
ルールの特殊性を使ってもう少し短くできるかちょっと思案してしまいます。

 #include<stdio.h>
 int main(){
	char i,d,s,u,m[10],*c="3331114201203602";
	while(scanf("%s",m)>0){
		d='d';
		for(i=0;i<8;i++){
			s=c[i+8]%8;
			u=m[s]|m[s+c[i]%8]|m[s+2*c[i]%8];
			d=(u&18)<17?u:d;
		}
		printf("%c\n",d);
	}
 }

----
*0067 The Number of Island
入力データの終了条件がよくわからないので何度も不正解を喰らってしまった問題。
問題自体は簡単だったし典型的な探索処理なのですが終了条件で手間取った。
なんか意地悪な問題。


 #include<stdio.h>
 int dxs[]={1,0,-1,0},dys[]={0,1,0,-1};
 char map[12][13];
 void saiki(int x,int y){
	int nx,ny;
	for(int i=0;i<4;i++){
		nx=x+dxs[i];
		ny=y+dys[i];
		if(nx<0 || 11<nx || ny<0 || 11<ny ||map[ny][nx]=='0') continue;
		map[ny][nx]='0';
		saiki(nx,ny);
	}
 }
 bool setMap(){
	for(int i=0;i<12;i++){
		if(scanf(" %12s",map[i])==EOF) return false;
    }
    int x,y,i,count=0;
    for(i=0;i<144;i++){
    	x=i%12;
    	y=i/12;
		if(map[y][x]=='1'){
			map[y][x]='0';
			count++;
			saiki(x,y);
		}
    }
    printf("%d\n",count);
    return true;
 }
 int main(){
	char s1;
	do{
		if(setMap()==false) break;
		if(scanf("%c",&s1)==EOF) break;
	}while(scanf("%c",&s1)!=EOF);
 }







----
*0068　Enclose Pins with a Rubber Band
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0068
一番外側を構成する線分に注目した時、線分を伸ばして直線にして平面を2分割した場合、他の点全てが平面のどちらかに集まるという特徴がある。
この条件を満たす線分を求めて後は共通集合で解。
　
　#include<stdio.h>
 void setData(int n){
	double xs[101],ys[101],vx1,vy1,vx2,vy2;
	bool hits[101];
	for(int i=0;i<n;i++){
		scanf("%lf,%lf",&xs[i],&ys[i]);
		hits[i]=false;
	}
	if(n<5){
		printf("%d\n",n-3);
		return ;
	}
	
	double d;
	for(int i=0;i<n-1;i++){
		for(int j=i+1;j<n;j++){
			if(j==i || (hits[i]&&hits[j])) continue;
			vx1=xs[j]-xs[i];
			vy1=ys[j]-ys[i];
			bool first=true;
			bool ok=true;
			for(int k=0;k<n;k++){
				if(i==k || j==k) continue;
				vx2=xs[k]-xs[i];
				vy2=ys[k]-ys[i];
				if(first==true){
					d=vx1*vy2-vx2*vy1;
					first=false;
				}else{
					if(d*(vx1*vy2-vx2*vy1)<=0){
						ok=false;
						break;
					}
				}
			}
			if(ok==true){
				hits[i]=hits[j]=true;
			}
		}
	}
	int ans=0;
	for(int i=0;i<n;i++){
		ans+=hits[i]?1:0;
	}
	printf("%d\n",n-ans);
 }
 int main(){
	int n;
	scanf("%d",&n);
	while(n!=0){
		setData(n);
		scanf("%d",&n);
	}
 }








----
*0069　Drawing Lots II
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0069
ただただ書いてある通りに愚直に実装。
0番台はやるだけ問題が多いな。



 #include<stdio.h>
 char map[31][13];
 bool  simulation(int now,int goal,int d){
	for(int i=0;i<d;i++){
		now+=map[i][now-1]=='1'?-1:map[i][now]=='1'?1:0;
	}
	return goal==now;
 }
 void setData(int n){
	int start,goal,d;
	scanf("%d %d %d",&start,&goal,&d);
	for(int i=0;i<d;i++){
		scanf("%s",&map[i][1]);
		map[i][0]=map[i][n]='0';
	}
	if(simulation(start,goal,d)==true){
		printf("0\n");
		return;
	}
	
	for(int i=0;i<d;i++){
		for(int j=1;j<n;j++){
			if(map[i][j-1]=='0' && map[i][j]=='0' && map[i][j+1]=='0'){
				map[i][j]='1';
				if(simulation(start,goal,d)==true){
					printf("%d %d\n",i+1,j);
					return;
				}
				map[i][j]='0';
			}
		}
	}
	printf("1\n");
 }
 int main(){
	int n;
	scanf("%d",&n);
	while(n!=0){
		setData(n);
		scanf("%d",&n);
	}
 }








----
*0070　Combination of Number Sequences
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0070
メモ化する方法を思いつかず全探索という最悪の方法で解く。
もっと賢い方法がありそうだけど？



 #include <stdio.h>
 void search(int deep ,int sum);
 int sums[11][331]={0};
 bool spentNos[11];
 int main(){
	for(int i=0;i<11;i++){
		spentNos[i]=false;
	}
	search(0,0);
	int n,s;
	while(scanf("%d %d",&n,&s)!=EOF){
		if(n>10 || s>330){
			printf("0\n");
		}else{
			printf("%d\n",sums[n][s]);
		}
	}
 }
 void search(int deep ,int sum){
	sums[deep][sum]++;
	if(deep==10){
		return ;
	}
	
	for(int i=0;i<10;i++){
		if(spentNos[i]==false){
			spentNos[i]=true;
			search(deep+1,sum+(deep+1)*i);
			spentNos[i]=false;
		}
	}
 }

*0061　Rank Checker
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0061
パソコン甲子園の参加チームの整理番号と得点が与えられます。
どのチームが何位だったか問われるので順位を表示するという問題です。

チームデータをベクターに確保し得点順にソートします。
これを上位から読み上位チームの番号と順位の組をＭａｐに保存します。
も少し賢い方法があるような気もしますが標準的に実装してみました。
これくらいならＥＸＣＥＬで計算した方が早そうです。


 #include<stdio.h>
 #include<vector>
 #include<map>
 #include <algorithm>
 struct team{
	int no,p;
	bool operator<(const team t)const {
		return p>t.p;
	}
 };
 int main(){
	std::vector<team> teams;
	team t;
	do{
		scanf("%d,%d",&t.no,&t.p);
		teams.push_back(t);
	}while(t.no!=0 && t.p!=0);
	std::sort(teams.begin(),teams.end());
	std::vector<team>::iterator it=teams.begin();
	int rank=1,p=(*it).p;
	std::map<int,int> memo;
	while(it!=teams.end()){
		if(p==(*it).p){
			memo[(*it).no]=rank;
		}else{
			p=(*it).p;
			rank++;
			memo[(*it).no]=rank;
		}
		it++;
	}
	while(scanf("%d",&p)!=EOF){
		printf("%d\n",memo[p]);
	}
 }





----
*0062 What is the Bottommost?
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0062
逆パスカルの三角形です。
一段ずつ足し算して最下段の数字を求めよという問題です。
解法
何列めの数字が最下段に行くまでに何回足されるかを計算するとcomになるという性質を利用します。

 #include<stdio.h>
 int main(){
	char t[11];
	int sum,com[]={1,10,45,120,210};
	while(scanf("%s",t)!=EOF){
		sum=0;
		for(int i=0;i<5;i++) sum+=com[i]*(t[i]+t[9-i]-96);
		printf("%d\n",sum%10);
	}
 }




----
*0063　Palindrome
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0063
英語の文字列が複数行与えられるので、逆から読んでも同じに読める文字を答えよという問題。
解法
普通に文字列を逆と手前から読んで、同じによめるならカウントしていくだけです。
stdには、配列をリバースするメソッドがあるのでそれを使うともっと簡単になるらしい。

 #include<stdio.h>
 #include<string.h>
 int main(){
	char text[101];
	bool ok;
	int len,ans=0;
	while(scanf("%s",text)!=EOF){
		ok=true;
		len=strlen(text);
		for(int i=0;i<len/2;i++){
			if(text[i]!=text[len-i-1]){
				ok=false;
				break;
			}
		}
		ans+=ok?1:0;
	}
	printf("%d\n",ans);
 }





----
*0064　Secret Number
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0064
状態遷移マシンを作って文字列を読み込みます。
数字に入れば数を10倍しながら読み込み数字から出たらsumをansに足しこみsumを0に戻します。
文字列末尾が数字で終わる場合に対処するためループ終了後sumを足すのを忘れないでください。
一行ずつでなく一文字ずつ読み込めば少しコードがシンプルになります。


 #include<stdio.h>
 #include<string.h>
 int main(){
	char t[81];
	int len,mod,sum=0,ans=0;
	while(scanf("%s",t)!=EOF){
		len=strlen(t);
		mod=0;
		sum=0;
		for(int i=0;i<len;i++){
			if('0'<=t[i] && t[i]<='9'){
				sum*=10;
				sum+=t[i]-'0';
			}else{
				ans+=sum;
				sum=0;
			}
		}
		ans+=sum;
	}
	printf("%d\n",ans);
 }





----
*0065　Trading
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0065
先月と今月の会社取引先データがあります。
両方に記録のある会社との取引回数を出力せよという問題です。

解法
今月の取引を記録し、先月の取引と照合して共通集合をとりカウントするだけです。
簡単なのでコードを見た方が早いでしょう。


 #include<stdio.h>
 #include<map>
 int main(){
	int no,day;
	char re[3];
	std::map<int,int> now,old;
	
	while(1){
		scanf("%d,%d",&no,&day);
		if(now.find(no)==now.end()){
			now[no]=1;
		}else{
			now[no]++;
		}
		scanf("%[\n]",re);
		if(re[1]!='\0') break;
	}
	while(scanf("%d,%d",&no,&day)!=EOF){
		if(old.find(no)==old.end()){
			old[no]=1;
		}else{
			old[no]++;
		}
	}
	std::map<int,int>::iterator it=old.begin();
	while(it!=old.end()){
		if(now.find((*it).first)!=now.end()){
			printf("%d %d\n",(*it).first,(*it).second+now[(*it).first]);
		}
		it++;
	}
 }






----
*0066 Tic Tac Toe
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0066
チックタックトゥ、ox(まるぺけ)の勝敗を判定せよという問題です。

解法
この問題はマトリックス*ｃを使って縦横斜めのチェックパターンを配置します。
チェックパターンを一つずつ読み込み、チェックする3マスの文字コードの|をとりuとします。
もし3マスともoかxならuは18でマスクをとった時2か16となります。
もし3マスがoxｓが混在すれば18でマスクをとった時18となりこれによって勝敗のチェックができます。

 #include<stdio.h>
 int main(){
	char i,d,s,u,m[10],*c="3331114201203602";
	while(scanf("%s",m)>0){
		d='d';
		for(i=0;i<8;i++){
			s=c[i+8]%8;
			u=m[s]|m[s+c[i]%8]|m[s+2*c[i]%8];
			d=(u&18)<17?u:d;
		}
		printf("%c\n",d);
	}
 }

----
*0067 The Number of Island
昔のＲＰＧ風の升目に島を表す1と海を表す0が与えられています。
マップの中にある島の数を数えて出力せよという問題です。
解法
ただ単に深さ優先探索をします。
升目を上から調べて、島があればその島のなかでいけるところを全て調べ海に戻します。
これを続けて島の数を数えれば答えが出ます。

 #include<stdio.h>
 int dxs[]={1,0,-1,0},dys[]={0,1,0,-1};
 char map[12][13];
 void saiki(int x,int y){
	int nx,ny;
	for(int i=0;i<4;i++){
		nx=x+dxs[i];
		ny=y+dys[i];
		if(nx<0 || 11<nx || ny<0 || 11<ny ||map[ny][nx]=='0') continue;
		map[ny][nx]='0';
		saiki(nx,ny);
	}
 }
 bool setMap(){
	for(int i=0;i<12;i++){
		if(scanf(" %12s",map[i])==EOF) return false;
    }
    int x,y,i,count=0;
    for(i=0;i<144;i++){
    	x=i%12;
    	y=i/12;
		if(map[y][x]=='1'){
			map[y][x]='0';
			count++;
			saiki(x,y);
		}
    }
    printf("%d\n",count);
    return true;
 }
 int main(){
	char s1;
	do{
		if(setMap()==false) break;
		if(scanf("%c",&s1)==EOF) break;
	}while(scanf("%c",&s1)!=EOF);
 }







----
*0068　Enclose Pins with a Rubber Band
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0068
平面上に点が与えられるので全ての点を囲むような一番外側の多角形を求め、その時多角形の内側に入る点の数を求めよという問題。
解法
一番外側を構成する線分の特徴として、線分を伸ばして直線にして平面を2分割した場合、線分を除く他の点全てが平面のどちらかに集まるという特徴があります。
この条件を満たす線分を求めて後は共通集合で解きます。
もう少し計算量を落とす方法としては、一点から始め一番外にある辺をたどっていくという手法があります。
　
　#include<stdio.h>
 void setData(int n){
	double xs[101],ys[101],vx1,vy1,vx2,vy2;
	bool hits[101];
	for(int i=0;i<n;i++){
		scanf("%lf,%lf",&xs[i],&ys[i]);
		hits[i]=false;
	}
	if(n<5){
		printf("%d\n",n-3);
		return ;
	}
	
	double d;
	for(int i=0;i<n-1;i++){
		for(int j=i+1;j<n;j++){
			if(j==i || (hits[i]&&hits[j])) continue;
			vx1=xs[j]-xs[i];
			vy1=ys[j]-ys[i];
			bool first=true;
			bool ok=true;
			for(int k=0;k<n;k++){
				if(i==k || j==k) continue;
				vx2=xs[k]-xs[i];
				vy2=ys[k]-ys[i];
				if(first==true){
					d=vx1*vy2-vx2*vy1;
					first=false;
				}else{
					if(d*(vx1*vy2-vx2*vy1)<=0){
						ok=false;
						break;
					}
				}
			}
			if(ok==true){
				hits[i]=hits[j]=true;
			}
		}
	}
	int ans=0;
	for(int i=0;i<n;i++){
		ans+=hits[i]?1:0;
	}
	printf("%d\n",n-ans);
 }
 int main(){
	int n;
	scanf("%d",&n);
	while(n!=0){
		setData(n);
		scanf("%d",&n);
	}
 }








----
*0069　Drawing Lots II
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0069
あみだくじを表すデータが与えられます。
指定のくじから始めて指定のゴールに辿りけるなら0を
横棒を一本つけ足してたどり着けるならその位置を。
つけ足してもたどり着けないなら1を出力せよという問題。

解法
書いてある通りに実装し、上から順に線を引いた場合を試していきます。
線を引いてはゴールにたどり着けるかsimulation関数で調べます、できないなら線を戻して次の線を引きます。
線を引けるかのチェックを忘れないでください。


 #include<stdio.h>
 char map[31][13];
 bool  simulation(int now,int goal,int d){
	for(int i=0;i<d;i++){
		now+=map[i][now-1]=='1'?-1:map[i][now]=='1'?1:0;
	}
	return goal==now;
 }
 void setData(int n){
	int start,goal,d;
	scanf("%d %d %d",&start,&goal,&d);
	for(int i=0;i<d;i++){
		scanf("%s",&map[i][1]);
		map[i][0]=map[i][n]='0';
	}
	if(simulation(start,goal,d)==true){
		printf("0\n");
		return;
	}
	
	for(int i=0;i<d;i++){
		for(int j=1;j<n;j++){
			if(map[i][j-1]=='0' && map[i][j]=='0' && map[i][j+1]=='0'){
				map[i][j]='1';
				if(simulation(start,goal,d)==true){
					printf("%d %d\n",i+1,j);
					return;
				}
				map[i][j]='0';
			}
		}
	}
	printf("1\n");
 }
 int main(){
	int n;
	scanf("%d",&n);
	while(n!=0){
		setData(n);
		scanf("%d",&n);
	}
 }








----
*0070　Combination of Number Sequences
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0070
ベクトルA(1,2,3,,,,n-1,n)
と0～9までの整数を使ったｎ個の整数の並びでできたベクトルK(k1,k2,,,kn)を考えます。
整数ｓが与えられるのでＡとＫの内積が整数sになるＫの組み合わせが何個あるか答えよという問題。
解法
賢い方法を思いつかなかったので全探索で解きました。



 #include <stdio.h>
 void search(int deep ,int sum);
 int sums[11][331]={0};
 bool spentNos[11];
 int main(){
	for(int i=0;i<11;i++){
		spentNos[i]=false;
	}
	search(0,0);
	int n,s;
	while(scanf("%d %d",&n,&s)!=EOF){
		if(n>10 || s>330){
			printf("0\n");
		}else{
			printf("%d\n",sums[n][s]);
		}
	}
 }
 void search(int deep ,int sum){
	sums[deep][sum]++;
	if(deep==10){
		return ;
	}
	
	for(int i=0;i<10;i++){
		if(spentNos[i]==false){
			spentNos[i]=true;
			search(deep+1,sum+(deep+1)*i);
			spentNos[i]=false;
		}
	}
 }