「AOJ1500~1509」の編集履歴(バックアップ)一覧に戻る

AOJ1500~1509 - (2013/01/12 (土) 19:49:46) のソース

*問い1500 ID
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1500
条件を満たすIDが幾通りあるか答える問題。

解法
-*の数も少なくメモ化で一発です。


 #include<stdio.h>
 #include<string.h>
 char id[100001];
 int memo[100001][10];
 int main(){
 	
 	int n,m,a;
 	int base2[10]={0,2,4,6,8,1,3,5,7,9};
 	bool oks[10]={0,0,0,0,0,0,0,0,0,0};
 	scanf("%d %s",&n,id);
 	scanf("%d",&m);
	for(int i=0;i<m;i++){
  		scanf("%d",&a);
		oks[a]=true;
  	}
 
 	memset(memo,0,sizeof(memo));
 	memo[0][0]=1;
 	for(int i=1;i<=n;i++){
 		char c=id[n-i];
 		if(c=='*'){
 			for(int j=0;j<=9;j++){
 				for(int k=0;k<=9;k++){
 					if(oks[k]==true){
 						if(i%2==0)memo[i][(j+base2[k])%10]+=memo[i-1][j];
 						else memo[i][(j+k)%10]+=memo[i-1][j];
 					}
 				}
 			}
 		}else{
 			for(int j=0;j<=9;j++){
 				if(i%2==0)memo[i][(j+base2[c-'0'])%10]+=memo[i-1][j];
 				else memo[i][(j+(c-'0'))%10]+=memo[i-1][j];
 			}
 		}
  	}
  	printf("%d\n",memo[n][0]);
 }








*1501 Grid
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1501
上端下端、左端右端がつながったマップで二点の間を最短距離で移動したとき何通りのルートがあるか。
解法
上下左右に斜めの8方向に向かった場合の最短距離を検討して後はメモ化計算で終わりです。

 #include<stdio.h>
 #include<algorithm>
 #include<string.h>
 #include<math.h>
  
 struct S{
 	int r,c,len;
 	bool operator<(const S& s)const{
 		return len<s.len;
 	}
 };
 int rootMemo[1002][1002];
 int mod=100000007;
 int calc(int r,int c){
 	memset(rootMemo,0,sizeof(rootMemo));
 	rootMemo[0][1]=1;
 	for(int i=1;i<=r+1;i++){
 		for(int j=1;j<=c+1;j++){
 			rootMemo[i][j]=rootMemo[i-1][j]+rootMemo[i][j-1];
 			if(rootMemo[i][j]>mod)rootMemo[i][j]-=mod;
  		}
 	}
 	return rootMemo[r+1][c+1];
 }
 
 int main(){
	S s[9];
 	int r,c,ys,xs,yg,xg,no;
 	scanf("%d %d %d %d %d %d",&r,&c,&ys,&xs,&yg,&xg);
 	xs++;
 	ys++;
 	xg++;
 	yg++;
 	for(int i=0;i<3;i++){
 		for(int j=0;j<3;j++){
 			no=i*3+j;
 			s[no].r=abs((ys+r)-(yg+r*i));
 			s[no].c=abs((xs+c)-(xg+c*j));
 			s[no].len=s[no].r+s[no].c;
 		}
 	}
 	std::sort(s,s+9);
 	int limit=s[0].len;
 	int ans=0;
 	for(int i=0;i<9;i++){
 		if(s[i].len>limit)break;
 		ans=(ans+calc(s[i].r,s[i].c))%mod;
 	}
 	printf("%d\n",ans);
 }








*1502 War
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1502
敵地へ攻め込んだ軍隊が敵地を占領するゲームの問題。

解法
遠くへいける兵士から優先して動かします。
第一陣の4人は先ず上下左右4方向へまっすぐ。
第二陣の4人は、一列ずれたところ1陣と平行にまっすぐ。
以下第n陣はn列ずれたところをまっすぐ進み全部いなくなるまでこれを続けるだけです。


 #include<stdio.h>
 #include<vector>
 #include<algorithm>
 #include<iostream>
 int main(){
 	std::vector<long long int> v;
 	long long int n,a,ans=1;
 	std::cin>>n;
 	while(n--){
 		std::cin>>a;
 		v.push_back(a);
 	}
 	std::sort(v.rbegin(),v.rend());
 	for(int i=0;i<v.size();i++){
 		ans+=v[i]-i/4>0?v[i]-i/4:0;
 	}
 	std::cout<<ans<<"\n";
 }