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

「AOJ2201~2210」の編集履歴(バックアップ)一覧に戻る
AOJ2201~2210」を以下のとおり復元します。
*2209 UTF-8
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2209

解法
下記コードと考え方はとりあえず解いただけというレベルです。
まず4バイト3バイト2バイト1バイトそれぞれで許される全パタンを1バイトずつ生成しstd::setに放り込みます。
そしてyが一つも1でないものと一つでも1があるかそもそもyがないものにし分けます。
次に文字列を全部読みこんだら、xの全パタンを一バイトずつ調べます。
4バイト3バイト2バイト1バイトに区切って1バイトずつメモ化計算で確定していきます。
この時バイトを一バイトずつに区切ってそれぞれで組み合わせを満たすか全探索します。
最後にyが全部0になる場合をひいたらそのバイトまでの計算は完了となります。
こんな汚い処理をせずとも多分調べたら綺麗なコードが世にたくさんあると思うので今から調べます。




 #include<stdio.h>
 #include<set>
 #include<string>
 #include<iostream>
 #include<string.h>
 std::set<std::string> patterns[5][4],patternsAllY0[5][4];//yがめんどくさいのでyの全パタンを最初に決定しておく
 
 long long int mod=1000000;
 
 void createCheckPattern(std::string str,int p,int no1,int no2,int yCount,bool hitY){
 	if(p==8){
 		if(yCount==0&&hitY==true)patternsAllY0[no1][no2].insert(str);
 		else patterns[no1][no2].insert(str);
 		return ;
 	}
 	
 	char c=str[p];
 	if(c=='x'||c=='y'){
 		str[p]='0';
 		bool hit=(c=='y');
 		createCheckPattern(str,p+1,no1,no2,yCount,hitY||hit);
 		str[p]='1';
 		createCheckPattern(str,p+1,no1,no2,yCount+hit,hitY||hit);
 		str[p]=c;
 	}else{
 		createCheckPattern(str,p+1,no1,no2,yCount,hitY);
 	}
 }
 
 void patternSet(){
 	createCheckPattern("0xxxxxxx",0,1,0,0,false);//1バイト
 	
 	createCheckPattern("110yyyyx",0,2,0,0,false);//2バイト1つめ文字
 	createCheckPattern("10xxxxxx",0,2,1,0,false);//2バイト2つ目
 	
 	createCheckPattern("1110yyyy",0,3,0,0,false);//3バイト1つ目
 	createCheckPattern("10yxxxxx",0,3,1,0,false);//3バイト2つ目
 	createCheckPattern("10xxxxxx",0,3,2,0,false);//3バイト3つ目
 	
 	createCheckPattern("11110yyy",0,4,0,0,false);//4バイト1つ目
 	createCheckPattern("10yyxxxx",0,4,1,0,false);//4バイト2つ目
 	createCheckPattern("10xxxxxx",0,4,2,0,false);//4バイト3つ目
 	createCheckPattern("10xxxxxx",0,4,3,0,false);//4バイト4つ目
 	/*for(int i=1;i<=4;i++){
 		for(int j=0;j<i;j++)printf("(%d %d %d)",patterns[i][j].size(),i,j);
 		printf("\n");
 		for(int j=0;j<i;j++)printf("(%d %d %d)",patternsAllY0[i][j].size(),i,j);
 		printf("\n\n");
 	}*/
 }
 
 void saiki(std::string& str,int p,int no1,int no2,long long int &re1,long long int& re2){
 	if(p==0)re1=re2=0;
 	if(p==8){
 		if(patterns[no1][no2].find(str)!=patterns[no1][no2].end())re1++;
 		else if(patternsAllY0[no1][no2].find(str)!=patternsAllY0[no1][no2].end())re2++;
 	}else{
 		if(str[p]=='x'){
 			str[p]='0';
 			saiki(str,p+1,no1,no2,re1,re2);
 			str[p]='1';
 			saiki(str,p+1,no1,no2,re1,re2);
 			str[p]='x';
 		}else{
 			saiki(str,p+1,no1,no2,re1,re2);
 		}
 	}
 }
 
 void calc(int n){
 	std::string strs[1002];
 	for(int i=0;i<n;i++){
 		std::cin>>strs[i];
	}
  	long long int memo[1010]={1,0};
 
 	for(int i=0;i<n;i++){
 		if(i+4<=n){
 			long long int ts[2][4];
 			memset(ts,0,sizeof(ts));
 			saiki(strs[i+0],0,4,0,ts[0][0],ts[1][0]);
 			saiki(strs[i+1],0,4,1,ts[0][1],ts[1][1]);
 			saiki(strs[i+2],0,4,2,ts[0][2],ts[1][2]);
 			saiki(strs[i+3],0,4,3,ts[0][3],ts[1][3]);
 			long long int t=0;
 			for(int s=0;s<2;s++){
 				for(int j=0;j<2;j++){
 					for(int k=0;k<2;k++){
 						for(int L=0;L<2;L++){
 							t+=ts[s][0]*ts[j][1]*ts[k][2]*ts[L][3];
 						}
 					}
 				}
 			}
 			t-=ts[1][0]*ts[1][1]*ts[0][2]*ts[0][3];
 			t%=mod;
 			memo[i+4]=(memo[i+4]+memo[i]*t)%mod;
  		}
 		if(i+3<=n){
 			long long int ts[2][4];
 			memset(ts,0,sizeof(ts));
 			saiki(strs[i+0],0,3,0,ts[0][0],ts[1][0]);
 			saiki(strs[i+1],0,3,1,ts[0][1],ts[1][1]);
 			saiki(strs[i+2],0,3,2,ts[0][2],ts[1][2]);
 			long long int t=0;
 			for(int s=0;s<2;s++){
 				for(int j=0;j<2;j++){
 					for(int k=0;k<2;k++){
 						t+=ts[s][0]*ts[j][1]*ts[k][2];
 					}
 				}
 			}
 			t-=ts[1][0]*ts[1][1]*ts[0][2];
 			t%=mod;
 			memo[i+3]=(memo[i+3]+memo[i]*t)%mod;
 		}
 		if(i+2<=n){
 			long long int ts[2][4];
 			memset(ts,0,sizeof(ts));
  			saiki(strs[i+0],0,2,0,ts[0][0],ts[1][0]);
 			saiki(strs[i+1],0,2,1,ts[0][1],ts[1][1]);
 			long long int t=0;
 			for(int s=0;s<2;s++){
 				for(int j=0;j<2;j++){
 					t+=ts[s][0]*ts[j][1];
 				}
 			}
 			t-=ts[1][0]*ts[0][1];
 			t%=mod;
 			memo[i+2]=(memo[i+2]+memo[i]*t)%mod;
 		}
 		if(i+1<=n){
 			long long int ts[2][4];
 			memset(ts,0,sizeof(ts));
 			long long int t=0;
 			saiki(strs[i],0,1,0,ts[0][0],ts[1][0]);
 			memo[i+1]=(memo[i+1]+memo[i]*ts[0][0])%mod;
 		}
 	}
 	std::cout<<memo[n]%mod<<"\n";
 }
 
 int main(){
 	int n;
 	patternSet();
 	char text[1000][10];
 	while(1){
 		scanf("%d",&n);
 		if(n==0)break;
 		calc(n);
 	}
 }

復元してよろしいですか?