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

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

AOJ2201~2210 - (2013/01/23 (水) 15:29:55) の最新版との変更点

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

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

 *2209 UTF-8
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2209
 バイトを表す文字列が与えられるので、それをUTF8エンコードで何通りの方法で表すことが出来るか。
 100万で割った数を答えよという問題。
 
 解法
 下記コードと考え方はとりあえず解いただけというレベルです。
 まず4バイト3バイト2バイト1バイトそれぞれで許される全パタンを1バイトずつのレベルで生成しstd::setに放り込みます。
 そしてyが一つも1でないものと一つでも1があるかそもそもyがないものにし分けます。
 次に文字列を全部読みこんだら、xの全パタンを一バイトずつ調べます。
 4バイト3バイト2バイト1バイトに区切って1バイトずつメモ化計算で確定していきます。
 この時バイトを一バイトずつに区切ってそれぞれで組み合わせを満たすか全探索します。
-最後にyが全部0になる場合をひいたらそのバイトまでの計算は完了となります。
+最後に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);
  	}
  }