AOJ521～530の編集履歴ソース - c21coterie @ ウィキ

AOJ521～530 - (2011/10/30 (日) 17:08:08) のソース

----
*0521 Change
釣銭枚数を計算する問題。
解法
書くだけです。

 #include<stdio.h>
 int main(){
	int n;
	while(1){
		scanf("%d",&n);
		if(n==0)break;
		n=1000-n;
		printf("%d\n",n/500+(n%500)/100+(n%100)/50+(n%50)/10+(n%10)/5+(n%5));
	}
 }



----
*0522 JOI and IOI
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0522
文字列の中からJOIとIOIの数を数える問題。

解法
文字列を前から見てカウントするだけです。
この問題では単語が短いので手抜きします。


 #include <stdio.h>
 int main(){
	char text[10001];
	while(scanf("%s",text)!=EOF){
		int ioi=0,joi=0;
		for(int i=0;text[i+2]!='\0';i++){
			if(text[i+1]=='O' && text[i+2]=='I'){
				if(text[i]=='J')joi++;
				if(text[i]=='I')ioi++;
			}
		}
		printf("%d\n%d\n",joi,ioi);
	}
 }


----
*0523　Card Game
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0523

解法
計算量が低いうえおそらくＮＰ困難問題なので愚直に実装します。
もしＮが大きくなった場合どうするか、少し考えつきません。


 #include <stdio.h>
 #include <string.h>
 void calc(int n){
	int nowCard;
	bool cards[2][201];
	memset(cards[0],false,201);
	memset(cards[1],true,201);
	for(int i=0;i<n;i++){
		scanf("%d",&nowCard);
		cards[0][nowCard]=true;
		cards[1][nowCard]=false;
	}
	int p,pturn=0,ans[2];
	ans[0]=ans[1]=n;
	while(1){
		p=1;
		while(p<=2*n){
			if(cards[pturn][p]){
				cards[pturn][p]=false;
				p++;
				ans[pturn]--;
				if(ans[pturn]==0)break;
				pturn=(pturn+1)%2;
			}else{
				p++;
			}
		}
		if(ans[pturn]==0)break;
		pturn=(pturn+1)%2;
	}	
	printf("%d\n%d\n",ans[1],ans[0]);
 }
 int main(){
	int n;
	while(1){
		scanf("%d",&n);
		if(n==0)break;
		calc(n);
	}
 }



----
*0524　Searching Constellation
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0524
平面上の星の座標データから星座を探す問題。

解法
一つずつ平行移動して重なるかチェックします。
星のポイントが整数であることを利用し、星の座標をsetに入れておくことで計算量をmlog(m)に下げます。



 #include<stdio.h>
 #include<set>
 struct point{
	int x,y;
	bool operator<(const point p)const{
		if(x!=p.x)return x<p.x;
		return y<p.y;
	}
 };
 void search(int m){
	point p;
	int xs[201],ys[201];
	for(int i=0;i<m;i++){
		scanf("%d %d",&xs[i],&ys[i]);
	}
	int n;
	scanf("%d",&n);
	std::set<point> allPs;
	std::set<point>::iterator it;
	for(int i=0;i<n;i++){
		scanf("%d %d",&p.x,&p.y);
		allPs.insert(p);
	}
	it=allPs.begin();
	bool allOK;
	int sx,sy;
	while(it!=allPs.end()){
		sx=(*it).x-xs[0];
		sy=(*it).y-ys[0];
		allOK=true;
		for(int i=0;i<m;i++){
			p.x=sx+xs[i];
			p.y=sy+ys[i];
			if(allPs.find(p)==allPs.end()){
				allOK=false;
				break;
			}
		}
		if(allOK==true){
			printf("%d %d\n",sx,sy);
			return;
		}
		it++;
	}
 }
 int main(){
	int m;
	while(1){
		scanf("%d",&m);
		if(m==0) break;
		search(m);
	}
 }




----
*0525　Osenbei
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0525
おせんべいをひっくり返してきちんと焼ける数を数える問題。

解法
横列の裏返しは2＾10通りしかなく、一度横列の裏表が決まれば最大化する方法は一通りしかないことを利用して解きます。
高速化する方法があるようですが私には思いつきませんでした。


 #include<stdio.h>
 #include<string.h>
 int map[11][10001];
 int remap[11][10001];
 int ans;
 int c,r;
 void saiki(int deep){
	if(deep==r){
		int count=0,temp;
		for(int x=0;x<c;x++){
			temp=0;
			for(int y=0;y<r;y++){
				temp+=remap[y][x];
			}
			temp=temp>r-temp?temp:r-temp;
			count+=temp;
		}
		ans=ans>count?ans:count;
	}else{
		memcpy(remap[deep],map[deep],4*10001);
		saiki(deep+1);
		for(int x=0;x<c;x++)remap[deep][x]=(map[deep][x]+1)%2;
		saiki(deep+1);
	}
 }
 void calc(){
	ans=0;
	for(int y=0;y<r;y++){
		for(int x=0;x<c;x++){
			scanf("%d",&map[y][x]);
		}
	}
	saiki(0);
	printf("%d\n",ans);
 }
 int main(){	
	while(1){
		scanf("%d %d",&r,&c);
		if(c==0 && r==0) break;
		calc();
	}
 }




----
*0526　Boat Travel
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0526
島から島へ渡る船舶の航路情報をもとに目的の島まで行く最小コストを求める問題です。
入力データの途中で航路情報が更新されるので、入力とともに航路データが変化します。
最短航路の更新作業を素早い実装にする必要があります。

解法
この問題最初航路データの更新をダイクストラ法を使って行いました。
当ページ掲載にあたりよりよいコード掲載のためにリンク先を基準にコードを書きなおしました。
http://www.ioi-jp.org/joi/2007/2008-yo-prob_and_sol/2008-yo-t6/review/2008-yo-t6-review.html


 #include<stdio.h>
 const int size=101;
 const int max=100000000;
 int cost[size][size];
 int n,k;
 void costUpData(int c,int d,int e){
	if(cost[c][d]<=e)return;
	int sum,sum2;
	cost[c][d]=cost[d][c]=e;
	for(int s=1;s<=n;s++){
		for(int g=1;g<=n;g++){
			sum=cost[s][c]+e+cost[d][g];
			if(sum<cost[s][g]) cost[s][g]=cost[g][s]=sum;
			sum=cost[s][d]+e+cost[c][g];
			if(sum<cost[s][g]) cost[s][g]=cost[g][s]=sum;
		}
	}
 }
 void calc(){
	for(int i=0;i<=n;i++){
		for(int j=0;j<=n;j++){
			cost[i][j]=max;
			if(i==j)cost[i][j]=0;
		}
	}
	int a,b,type,c,d,e;
	for(int i=0;i<k;i++){
		scanf("%d",&type);
		if(type==0){
			scanf("%d %d",&a,&b);
			printf("%d\n",cost[a][b]==max?-1:cost[a][b]);
		}else{
			scanf("%d %d %d",&c,&d,&e);
			costUpData(c,d,e);
		}
	}
 }
 int main(){
	while(1){
		scanf("%d %d",&n,&k);
		if(n==0 &&k==0) break;
		calc();
	}
 }





----
*0527　Setting Go Stones
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0527

碁石の置き換え問題。
解法
連続して同色の碁石が並んでいる部分を塊で扱います。




 #include<stdio.h>
 #include<vector>
 struct stone{
	int count,color;
 };
 void calc(int n){
	std::vector<stone> stones;
	stone s;
	int color,last;
	for(int i=1;i<=n;i++){
		scanf("%d",&s.color);
		s.count=1;
		last=stones.size()-1;
		if(i%2==1){
			if(stones.empty()){
				stones.push_back(s);
			}else if(stones[last].color==s.color){
				stones[last].count++;
			}else{
				stones.push_back(s);
			}			
		}else{
			color=stones[last].color;
			if(color==s.color){
				stones[last].count++;
			}else{
				s=stones[last];
				stones.pop_back();
				if(stones.empty()){
					s.color=(s.color+1)%2;
					s.count++;
					stones.push_back(s);
				}else{
					stones[last-1].count+=s.count+1;
				}
			}
		}
	}
	int ans=0;
	for(int i=0;i<stones.size();i++){
		if(stones[i].color==0)ans+=stones[i].count;
	}
	printf("%d\n",ans);
 }
 int main(){
	int n;
	while(1){
		scanf("%d",&n);
		if(n==0) break;
		calc(n);
	}
 }




----
*0528　Common Sub-String
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0528
最長一致部分文字列を探す問題。
解法
動的計画法でn^2の計算量で解きます。


 #include<stdio.h>
 #include<string.h>
 int main(){
	char text[4001],text2[4001];
	int memo[2][4003],now,old,ans;
	while(scanf("%s",text)!=EOF){
		memset(memo,0,sizeof(memo));
		scanf("%s",text2);
		ans=0;
		for(int i=0;text2[i]!='\0';i++){
			now=i%2;
			old=(i+1)%2;
			memset(memo[now],0,4003*4);
			for(int j=0;text[j]!='\0';j++){
				if(text2[i]==text[j]){
					memo[now][j+1]=memo[old][j]+1;
					ans=ans>memo[now][j+1]?ans:memo[now][j+1];
				}
			}
		}
		printf("%d\n",ans);
	}
 }



----
*0529　Darts
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0529
ダーツを4回投げたときＭを超えない可能な最高得点を探す問題。

解法
きれいなコードを用意できませんでした。
1本投げた場合を求め、次に2本投げた場合の全組み合わせを求め、Ｖｅｃｔｏｒに保存しておきます。
後は3本の組を1本のセットと2本のセットからバイナリサーチで最高点を求め、4本は2本+2本をバイナリサーチで求めます。

正答者データを見る限りこの問題は下記コードの半分程度のコード量で正答できさらなる高速化も可能なようです。
正答者データ一覧↓
http://judge.u-aizu.ac.jp/onlinejudge/problem_statistics.jsp?id=0529



 #include <stdio.h>
 #include <vector>
 #include <algorithm>
 int solve(int n,int m);
 int main()
 {
	int n,m,ans;
	scanf("%d %d",&n,&m);
	while(n!=0 && m!=0){
		ans=solve(n,m);
		printf("%d\n",ans);
		scanf("%d %d",&n,&m);
	}
 }
 int bsearch(std::vector<int> &v,int target){
	int l=0,r=v.size(),size=v.size()-1;
	if(v[0]>target) return 0;
	if(v[size]<=target) return v[size];
	int index;
	while(1){
		index=(l+r)/2;
		if(v[index]==target) return target;
		if(index<size && v[index]<target && v[index+1]>target) return v[index];
		if(v[index]>target){
			r=index;
			continue;
		}
		if(v[index]<target){
			l=index+1;
			continue;
		}
	}
	return -1;
 }
 int solve(int n,int m)
 {
	std::vector<int> wPoints;
	std::vector<int>::iterator it;
	int t;
	int datas[1001];
	int p=0;
	int ans=0;
	//一本だけ使う場合	
	for(int i=0;i<n;i++)
	{
		scanf("%d",&t);
		if(t==m){
			return m;
		}else if(t<m){
			datas[p]=t;
			p++;
			ans=std::max(ans,t);
		}
	}
	//2本使う場合
	for(int i=0;i<p;i++){
		for(int j=0;j<=i;j++){
			t=datas[i]+datas[j];
			if(t==m){
				return m;
			}else if(t<m){
				wPoints.push_back(t);
				ans=std::max(ans,t);
			}
		}
	}
	std::sort(wPoints.begin(),wPoints.end());	
	//3本使う場合
	for(int i=0;i<p;i++){
		t=m-datas[i];
		t=datas[i]+bsearch(wPoints,t);
		ans=std::max(ans,t);
		if(ans==m) return m;
	}
	//4本使う場合
	it=wPoints.begin();
	while(it!=wPoints.end())
	{
		t=m-(*it);
		//if(t<(*it)) return ans;
		t=(*it)+bsearch(wPoints,t);
		ans=std::max(ans,t);
		if(ans==m) return m;
		it++;
	}
	return ans;
 }



----
*0530　Pyon-Pyon River Crossing
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0530
川の上に出た石から石へジャンプして川を渡るとき、最も安全なルートをとった場合の危険度を算出する問題。
解法
一行ずつ動的計画法で計算し一番安全なルート以外枝刈していきます。
2段飛ばしジャンプができる回数の制限があるために3次元必要になる点に注意が必要です。



 #include<stdio.h>
 #include<vector>
 #include <stdlib.h>
 int n,m;
 struct Stone{
	int x,d;//ｘ座標と滑りやすさ
 };
 void calc(){
	int memo[77][154][11];//動的計画法である石に到達したとき滑りやすさの合計が最小となる経路を残す
	std::vector<Stone> stones[154];
	Stone stone;
	int k;//滑りやすさ
	int max=1000000000;
	for(int z=0;z<=(n+1)/2;z++){
		for(int y=0;y<n;y++){
			for(int x=0;x<11;x++){
				
				if	(y==1 && z==1)   memo[1][y][x]=0;
				else if (y==0 && z==0)	 memo[0][y][x]=0;
				else 			 memo[z][y][x]=max;
			}
		}
	}	
	for(int y=0;y<n;y++){
		scanf("%d",&k);
		for(int j=0;j<k;j++){
			scanf("%d %d",&stone.x,&stone.d);
			stones[y].push_back(stone);
		}
	}
	int jump,slip;	
	for(int y=0;y<n-1;y++){
		jump=(y+1)/2>m?m:(y+1)/2;
		for(int z=0;z<=jump;z++){
			for(unsigned int x=0;x<stones[y].size();x++){
				//一段ジャンプ
				for(unsigned int x2=0;x2<stones[y+1].size();x2++){
					slip=memo[z][y][x]+abs(stones[y][x].x-stones[y+1][x2].x)*(stones[y][x].d+stones[y+1][x2].d);
					if(memo[z][y+1][x2]>slip){
						memo[z][y+1][x2]=slip;
					}
				}
				//2段ジャンプ
				for(unsigned int x2=0;x2<stones[y+2].size();x2++){
					slip=memo[z][y][x]+abs(stones[y][x].x-stones[y+2][x2].x)*(stones[y][x].d+stones[y+2][x2].d);
					if(memo[z+1][y+2][x2]>slip){
						memo[z+1][y+2][x2]=slip;
					}
				}
			}
		}
	}
	int ans=max;
	for(int z=0;z<=m;z++){
			for(int x=0;x<11;x++){
				ans=memo[z][n-1][x]<ans?memo[z][n-1][x]:ans;
				if(z==m) continue;
				ans=memo[z][n-2][x]<ans?memo[z][n-2][x]:ans;
			}
	}
	printf("%d\n",ans);
 }
 int main(){
	while(1){
		scanf("%d %d",&n,&m);
		if(n==0 && m==0) break;
		calc();
	}
 }
c21coterie @ ウィキ

AOJ521～530

更新履歴

メニュー

リンク

他のサービス

AOJ521～530 - (2011/10/30 (日) 17:08:08) のソース
