「AOJ2201～2210」の編集履歴（バックアップ）一覧に戻る
AOJ2201～2210 - (2013/01/23 (水) 15:30:59) のソース
*2209 UTF-8
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2209
バイトを表す文字列が与えられるので、それをＵＴＦ8エンコードで何通りの方法で表すことが出来るか。
100万で割った数を答えよという問題。
解法
下記コードと考え方はとりあえず解いただけというレベルです。
まず4バイト3バイト2バイト1バイトそれぞれで許される全パタンを1バイトずつのレベルで生成しstd::setに放り込みます。
そしてｙが一つも１でないものと一つでも1があるかそもそもｙがないものにし分けます。
次に文字列を全部読みこんだら、ｘの全パタンを一バイトずつ調べます。
4バイト3バイト2バイト1バイトに区切って1バイトずつメモ化計算で確定していきます。
この時バイトを一バイトずつに区切ってそれぞれで組み合わせを満たすか全探索します。
最後にｙの部分が全部0になってる禁止ケースになってる場合をひいたらそのバイトまでの計算は完了となります。
こんな汚い処理をせずとも多分調べたら綺麗なコードが世にたくさんあると思うので今から調べようと思います。
来年までにはもっとかっこいいコードが書けるようになりたいなあ。
#include<stdio.h>
#include<set>
#include<string>
#include<iostream>
#include<string.h>
std::set<std::string> patterns[5][4],patternsAllY0[5][4];//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);//２バイト２つ目
createCheckPattern("1110yyyy",0,3,0,0,false);//３バイト１つ目
createCheckPattern("10yxxxxx",0,3,1,0,false);//３バイト2つ目
createCheckPattern("10xxxxxx",0,3,2,0,false);//３バイト3つ目
createCheckPattern("11110yyy",0,4,0,0,false);//4バイト１つ目
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);
}
}
