※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

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

AOJ1500~1509 - (2013/01/21 (月) 18:30:55) の1つ前との変更点

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

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

 *問い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";
  }
 
 
 
 
 
 *1507 Dungeon (II)
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1507
 ゲームのダンジョンの危険度を判定する問題。
 
 解法
 只今考え中。
-いったん全部の点を切ってコストの低い辺から繋げていきます。
-繋げたことで木構造がつながっていきますが、この時片側の木にある点から反対側の木にある点に移動するにはどの点を選んでも、繋げた辺のコストだけコストがかかります。
+いったん全部の辺を切ってコストの低い辺から繋げていきます。
+繋げたことで木構造がつながっていきますが、この時つながった木の片側の木にある点から反対側の木にある点に移動するにはどの点を選んでも、繋げた辺のコストだけコストがかかります。
 なのでこの繋げた時に発生したコストを足し算してやれば計算が終わるのですが、問題はどうやって繋げたを表現するかです。