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

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

AOJ1500~1509 - (2013/01/12 (土) 18:02:38) の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]);
+ }