「AOJ2201~2210」の編集履歴(バックアップ)一覧はこちら
「AOJ2201~2210」(2013/01/23 (水) 15:30:59) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
*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になる場合をひいたらそのバイトまでの計算は完了となります。
こんな汚い処理をせずとも多分調べたら綺麗なコードが世にたくさんあると思うので今から調べようと思います。
来年までにはもっとかっこいいコードが書けるようになりたいなあ。
#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);
}
}
*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になってる禁止ケースになってる場合をひいたらそのバイトまでの計算は完了となります。
こんな汚い処理をせずとも多分調べたら綺麗なコードが世にたくさんあると思うので今から調べようと思います。
来年までにはもっとかっこいいコードが書けるようになりたいなあ。
#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);
}
}