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

UVa100～110 - (2013/03/13 (水) 17:35:02) の１つ前との変更点

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

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

*問い100
初めてのＵＶaですが解いてみたらコード実行速度3892/74613位。
上位5％近辺に入れて悪くないスタートですが、私は英語がほとんどできないので他の問題も解けるかは不明。


 #include<stdio.h>
 #include<string.h>
 int memo[1000*1000+1];
 
 int saiki(unsigned int n){
 	if(n<=1000*1000&&memo[n]!=-1){
 		return memo[n]+1;
 	}else{
 		int no=saiki(n%2==1?3*n+1:n/2);
 		if(n<=1000*1000)memo[n]=no;
 		return no+1;
 	}
 }
 
 int main(){
 	memset(memo,-1,sizeof(memo));
 	memo[1]=1;
 	for(int i=2;i<=1000*1000;i++){
 		if(memo[i]==-1)memo[i]=saiki(i%2==1?3*i+1:i/2);
 	}
 	int a,b;
 	while(scanf("%d",&a)!=EOF){
 		if(scanf("%d",&b)==EOF)break;
 		int max=0;
 		if(a<=b)for(int i=a;i<=b;i++)if(max<memo[i])max=memo[i];
 		if(b<=a)for(int i=b;i<=a;i++)if(max<memo[i])max=memo[i];
 		printf("%d %d %d\n",a,b,max);
 	}
 }


*問い101 - The Blocks Problem
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=37
アームロボットにブロックの移動命令が与えられる。
移動後のブラックの状態を答えよという問題。




 #include<stdio.h>
 #include<vector>
 #include<string>
 #include<iostream>
 //私は英語が苦手なため何度もＷＡになってから題意をつかむという状態です。
 //必然的に正答率は非常に低くなります
 std::vector<int> bs[25];
 int main(){
 	int n,a,b;
 	scanf("%d",&n);
 	for(int i=0;i<n;i++)bs[i].push_back(i);
 	std::string com1,com2;
 	while(1){
 		std::cin>>com1;
 		if(com1=="quit")break;
 		std::cin>>a>>com2>>b;
 		int no1,no2;
 		std::vector<int>::iterator it1,it2,it3;
 		for(int i=0;i<n;i++){
 			for(std::vector<int>::iterator it=bs[i].begin();it!=bs[i].end();it++){
 				if((*it)==b){
 					no2=i;//b置かれる場所
 					it2=it;
 				}
 				if((*it)==a){
 					it1=it;//a置くもの
 					no1=i;
 				}
 			}
 		}
 		if(no1==no2)continue;
 		if(com1=="move"&&com2=="onto"){
 			it2++;
 			it2=bs[no2].insert(it2,(*it1));
 			it2++;
 			it1=bs[no1].erase(it1);
 			while(it2!=bs[no2].end()){
 				bs[(*it2)].push_back((*it2));
 				it2=bs[no2].erase(it2);
 			}
 			while(it1!=bs[no1].end()){
 				bs[(*it1)].push_back((*it1));
 				it1=bs[no1].erase(it1);
 			}
 		}
 		if(com1=="move"&&com2=="over"){
 			bs[no2].push_back((*it1));
 			it1=bs[no1].erase(it1);
 			while(it1!=bs[no1].end()){
 				bs[(*it1)].push_back((*it1));
 				it1=bs[no1].erase(it1);
 			}
 		}
 		if(com1=="pile"&&com2=="onto"){
 			it2++;
 			it3=it1;
 			while(it1!=bs[no1].end()){
 				it2=bs[no2].insert(it2,(*it1));
 				it2++;
 				it1++;
 			}
 			while(it2!=bs[no2].end()){
 				bs[(*it2)].push_back((*it2));
 				it2=bs[no2].erase(it2);
 			}
 			
 			bs[no1].erase(it3,bs[no1].end());
 		}
 		if(com1=="pile"&&com2=="over"){
 			bs[no2].insert(bs[no2].end(),it1,bs[no1].end());
 			bs[no1].erase(it1,bs[no1].end());
 		}
 	}
 	for(int i=0;i<n;i++){
 		printf("%d:",i);
 		for(int j=0;j<bs[i].size();j++){
 			printf(" %d",bs[i][j]);
 		}
 		printf("\n");
 	}
 }  





*102 Ecological Bin Packing 
http://uva.onlinejudge.org/external/1/102.html
ビンを分けるらしいのだがよくわからなかった問題。

1682/17942位獲得。
題意がよくわからなかったので検索したら中国語の正答コード掲載ブログが出てきた。
ブログを読んでもやはり良くわからなかったので参考にコードを縮めれないか試したくらい。
この問題で速度差が出るとは思えないので同順位多数ということだと思う。

 #include<stdio.h> 
 int main(){
 	int b1,c1,g1,b2,c2,g2,b3,c3,g3,ws[6];
  	char ansCom[6][4]={"BCG","BGC","CBG","CGB","GBC","GCB"};
 	while(1){
 		int sum;
 		if(scanf("%d %d %d %d %d %d %d %d %d",&b1,&g1,&c1,&b2,&g2,&c2,&b3,&g3,&c3)==EOF)return 0;
 		sum=b1+c1+g1+b2+g2+c2+b3+g3+c3;
  		ws[0]=b1+c2+g3;
 		ws[1]=b1+g2+c3;
 		ws[2]=c1+b2+g3;
 		ws[3]=c1+g2+b3;
 		ws[4]=g1+b2+c3;
 		ws[5]=g1+c2+b3;
 		int max=ws[0],no=0;
 		for(int i=0;i<6;i++){
  			if(max<ws[i]){
 				max=ws[i];
 				no=i;
 			}
 		}
 		printf("%s %d\n",ansCom[no],sum-max);
 	}
 }






*105- The Skyline Problem
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=41
y=0を床とする平面の上に長方形が置かれている。
長方形の高さに変化があった場所を表示せよという問題。
コード実行速度325/6697位を獲得。
何一つ工夫しないで素朴に実装しただけなのに何故こんなに高ランクになってんだろ？



 #include<stdio.h>
 #include<algorithm>
 #include<map>
 #include<vector>
 const int OUT=1,IN=0;
 
 struct S{
 	int x,h,type;
 	bool operator<(const S& s)const{
 		if(x!=s.x)return x<s.x;
 		return type>s.type;
 	}
 };
 
 int main(){
 	int nowX;
 	std::map<int,int> memo;
 	std::map<int,int>::iterator it;
 	std::vector<S> datas;
 	S s1;
 	int a,b,h;
 	while(scanf("%d",&a)!=EOF){
  		scanf("%d %d",&h,&b);
 		s1.x=a;
 		s1.h=h;
 		s1.type=IN;
 		datas.push_back(s1);
 		s1.x=b;
 		s1.type=OUT;
 		datas.push_back(s1);
 	}
 	std::sort(datas.begin(),datas.end());
 	nowX=datas[0].x;
 	int no=0,nowH=0;
 	while(no<datas.size()){
 		while(no<datas.size()&&nowX==datas[no].x){
  			s1=datas[no];
			if(s1.type==OUT){
 				memo[s1.h]--;
  			}else{
 				memo[s1.h]++;
 			}
 			if(memo[s1.h]<=0)memo.erase(s1.h);
 			nowX=s1.x;
 			no++;
 		}
 		if(datas.size()<=no)break;
 		it=memo.end();
 		if(it!=memo.begin())it--;
 		if(nowH!=(*it).first){
 			printf("%d %d ",nowX,(*it).first);
 			nowH=(*it).first;
 		}
 		nowX=datas[no].x;
 	}
 	printf("%d 0\n",nowX);
 }

*問い100
初めてのＵＶaですが解いてみたらコード実行速度3892/74613位。
上位5％近辺に入れて悪くないスタートですが、私は英語がほとんどできないので他の問題も解けるかは不明。


 #include<stdio.h>
 #include<string.h>
 int memo[1000*1000+1];
 
 int saiki(unsigned int n){
 	if(n<=1000*1000&&memo[n]!=-1){
 		return memo[n]+1;
 	}else{
 		int no=saiki(n%2==1?3*n+1:n/2);
 		if(n<=1000*1000)memo[n]=no;
 		return no+1;
 	}
 }
 
 int main(){
 	memset(memo,-1,sizeof(memo));
 	memo[1]=1;
 	for(int i=2;i<=1000*1000;i++){
 		if(memo[i]==-1)memo[i]=saiki(i%2==1?3*i+1:i/2);
 	}
 	int a,b;
 	while(scanf("%d",&a)!=EOF){
 		if(scanf("%d",&b)==EOF)break;
 		int max=0;
 		if(a<=b)for(int i=a;i<=b;i++)if(max<memo[i])max=memo[i];
 		if(b<=a)for(int i=b;i<=a;i++)if(max<memo[i])max=memo[i];
 		printf("%d %d %d\n",a,b,max);
 	}
 }


*問い101 - The Blocks Problem
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=37
アームロボットにブロックの移動命令が与えられる。
移動後のブラックの状態を答えよという問題。




 #include<stdio.h>
 #include<vector>
 #include<string>
 #include<iostream>
 //私は英語が苦手なため何度もＷＡになってから題意をつかむという状態です。
 //必然的に正答率は非常に低くなります
 std::vector<int> bs[25];
 int main(){
 	int n,a,b;
 	scanf("%d",&n);
 	for(int i=0;i<n;i++)bs[i].push_back(i);
 	std::string com1,com2;
 	while(1){
 		std::cin>>com1;
 		if(com1=="quit")break;
 		std::cin>>a>>com2>>b;
 		int no1,no2;
 		std::vector<int>::iterator it1,it2,it3;
 		for(int i=0;i<n;i++){
 			for(std::vector<int>::iterator it=bs[i].begin();it!=bs[i].end();it++){
 				if((*it)==b){
 					no2=i;//b置かれる場所
 					it2=it;
 				}
 				if((*it)==a){
 					it1=it;//a置くもの
 					no1=i;
 				}
 			}
 		}
 		if(no1==no2)continue;
 		if(com1=="move"&&com2=="onto"){
 			it2++;
 			it2=bs[no2].insert(it2,(*it1));
 			it2++;
 			it1=bs[no1].erase(it1);
 			while(it2!=bs[no2].end()){
 				bs[(*it2)].push_back((*it2));
 				it2=bs[no2].erase(it2);
 			}
 			while(it1!=bs[no1].end()){
 				bs[(*it1)].push_back((*it1));
 				it1=bs[no1].erase(it1);
 			}
 		}
 		if(com1=="move"&&com2=="over"){
 			bs[no2].push_back((*it1));
 			it1=bs[no1].erase(it1);
 			while(it1!=bs[no1].end()){
 				bs[(*it1)].push_back((*it1));
 				it1=bs[no1].erase(it1);
 			}
 		}
 		if(com1=="pile"&&com2=="onto"){
 			it2++;
 			it3=it1;
 			while(it1!=bs[no1].end()){
 				it2=bs[no2].insert(it2,(*it1));
 				it2++;
 				it1++;
 			}
 			while(it2!=bs[no2].end()){
 				bs[(*it2)].push_back((*it2));
 				it2=bs[no2].erase(it2);
 			}
 			
 			bs[no1].erase(it3,bs[no1].end());
 		}
 		if(com1=="pile"&&com2=="over"){
 			bs[no2].insert(bs[no2].end(),it1,bs[no1].end());
 			bs[no1].erase(it1,bs[no1].end());
 		}
 	}
 	for(int i=0;i<n;i++){
 		printf("%d:",i);
 		for(int j=0;j<bs[i].size();j++){
 			printf(" %d",bs[i][j]);
 		}
 		printf("\n");
 	}
 }  





*102 Ecological Bin Packing 
http://uva.onlinejudge.org/external/1/102.html
ビンを分けるらしいのだがよくわからなかった問題。

1682/17942位獲得。
題意がよくわからなかったので検索したら中国語の正答コード掲載ブログが出てきた。
ブログを読んでもやはり良くわからなかったので参考にコードを縮めれないか試したくらい。
この問題で速度差が出るとは思えないので同順位多数ということだと思う。

 #include<stdio.h> 
 int main(){
 	int b1,c1,g1,b2,c2,g2,b3,c3,g3,ws[6];
  	char ansCom[6][4]={"BCG","BGC","CBG","CGB","GBC","GCB"};
 	while(1){
 		int sum;
 		if(scanf("%d %d %d %d %d %d %d %d %d",&b1,&g1,&c1,&b2,&g2,&c2,&b3,&g3,&c3)==EOF)return 0;
 		sum=b1+c1+g1+b2+g2+c2+b3+g3+c3;
  		ws[0]=b1+c2+g3;
 		ws[1]=b1+g2+c3;
 		ws[2]=c1+b2+g3;
 		ws[3]=c1+g2+b3;
 		ws[4]=g1+b2+c3;
 		ws[5]=g1+c2+b3;
 		int max=ws[0],no=0;
 		for(int i=0;i<6;i++){
  			if(max<ws[i]){
 				max=ws[i];
 				no=i;
 			}
 		}
 		printf("%s %d\n",ansCom[no],sum-max);
 	}
 }




*問い103
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=39
ｄ次元空間の箱を別の箱に入れて入れ子にしていく時もっともたくさんたくさん入る入れ子を出力せよという問題。
箱は回転しても良いがどのへんも次元の軸と平行でなくてはいけない。
例えば３次元なら箱のどの辺もＸ軸、Ｙ軸、Ｚ軸のどれかと平行でなくてはいけない。

解法
箱が別の箱に入る関係を半順序集合のグラフとして表現。
箱の回転は回転行列の概念より2この座標を入れ替えるのと同じなので全ての組み合わせを考えることが出来る。
5,4,3,2,1の長さで表される箱なら5,4,3,2,1を並べ替えたすべての組み合わせとして表現することが出来る。
後はダイクストラ法もどきで解決。


 #include<stdio.h>
 #include<vector>
 #include<algorithm>
 #include<set>
 bool isInOk(std::vector<int> q1,std::vector<int> q2){
 	//ベクターはソート済みであると仮定
 	std::vector<int>::iterator it;
 	for(int i=0;i<q1.size();i++){
 		it=std::upper_bound( q2.begin(), q2.end(), q1[i] );
 		if(it==q2.end())return false;
 		q2.erase(it);
 	}
 	return true;
 }
 
 void upData(std::vector<int>& ansA,std::vector<int>& ansB){
 	if(ansA.size()<ansB.size()){
 		ansA.clear();
 		ansA.insert(ansA.begin(),ansB.begin(),ansB.end());
 	}
 }
 
 int main(){
 	
 	int n,d,l;
 	while(scanf("%d %d",&n,&d)!=EOF){
 		std::vector<int> qs[31],ans[31],lastAns;
  		std::set<int> G[31];
 		std::set<int>::iterator it;
 		for(int i=0;i<n;i++){
 			for(int j=0;j<d;j++){
 				scanf("%d",&l);
 				qs[i].push_back(l);
 			}
 			std::sort(qs[i].begin(),qs[i].end());
  			ans[i].push_back(i);
 		}
 		for(int i=0;i<n;i++){
 			for(int j=0;j<n;j++){
 				if(i==j)continue;
 				if(isInOk(qs[i],qs[j])==true){
  					//ｊの中にiが入った
 					G[j].insert(i);
 				}
 			}
 		}
 		int spents[31]={0};
 		for(int i=0;i<n;i++){
  			std::vector<int> dells;
 			for(int j=0;j<n;j++){
 				if(G[j].empty()==true&&spents[j]==0){
 					dells.push_back(j);
 					spents[j]=1;
 				}
 			}
 			if(dells.empty()==true)break;
 			for(int j=0;j<dells.size();j++){
 				int no=dells[j];
  				for(int k=0;k<n;k++){
 					if(G[k].find(no)!=G[k].end()){
 						ans[no].push_back(k);
 						upData(ans[k],ans[no]);
 						ans[no].pop_back();
 						G[k].erase(no);
 					}
 				}
 			}
 		}
 		for(int i=0;i<n;i++){
 			if(lastAns.size()<ans[i].size()){
 				lastAns.clear();
 				lastAns.insert(lastAns.begin(),ans[i].begin(),ans[i].end());
 			}
 		}
 		printf("%d\n",lastAns.size());
 		for(int i=0;i<lastAns.size();i++){
 			printf("%d",lastAns[i]+1);
 			if(i<lastAns.size()-1)printf(" ");
 		}
 		printf("\n");
 	}
 }







*105- The Skyline Problem
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=41
y=0を床とする平面の上に長方形が置かれている。
長方形の高さに変化があった場所を表示せよという問題。
コード実行速度325/6697位を獲得。
何一つ工夫しないで素朴に実装しただけなのに何故こんなに高ランクになってんだろ？



 #include<stdio.h>
 #include<algorithm>
 #include<map>
 #include<vector>
 const int OUT=1,IN=0;
 
 struct S{
 	int x,h,type;
 	bool operator<(const S& s)const{
 		if(x!=s.x)return x<s.x;
 		return type>s.type;
 	}
 };
 
 int main(){
 	int nowX;
 	std::map<int,int> memo;
 	std::map<int,int>::iterator it;
 	std::vector<S> datas;
 	S s1;
 	int a,b,h;
 	while(scanf("%d",&a)!=EOF){
  		scanf("%d %d",&h,&b);
 		s1.x=a;
 		s1.h=h;
 		s1.type=IN;
 		datas.push_back(s1);
 		s1.x=b;
 		s1.type=OUT;
 		datas.push_back(s1);
 	}
 	std::sort(datas.begin(),datas.end());
 	nowX=datas[0].x;
 	int no=0,nowH=0;
 	while(no<datas.size()){
 		while(no<datas.size()&&nowX==datas[no].x){
  			s1=datas[no];
			if(s1.type==OUT){
 				memo[s1.h]--;
  			}else{
 				memo[s1.h]++;
 			}
 			if(memo[s1.h]<=0)memo.erase(s1.h);
 			nowX=s1.x;
 			no++;
 		}
 		if(datas.size()<=no)break;
 		it=memo.end();
 		if(it!=memo.begin())it--;
 		if(nowH!=(*it).first){
 			printf("%d %d ",nowX,(*it).first);
 			nowH=(*it).first;
 		}
 		nowX=datas[no].x;
 	}
 	printf("%d 0\n",nowX);
 }