HackerRank Weekly Challenges - Week 4 5問目
problem statement(コンテストページ)
problem statement
長さ $N$ の数字のみからなる文字列 $S$ が与えられる.
この文字列 $S$ の部分文字列で,(leading zerosはないとして)$2^x\ (x=0,1,\ldots,800)$ となるものが合計で何個あるかを求める問題.
Aho Corasickすれば良い.
一度オートマトンを作れば,テストケースごとに作り直す必要はない.
オートマトンの構築に時間計算量がだいたい $2^x$ の文字列の長さの和,後は各テストケースごとに時間計算量 $O(N)$ でできる.
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)
#define ll long long
typedef struct AhoCorasick_struct{
int nodeMemory, alphabetMemory;
int nodeSize, alphabetSize, wordSize;
int **next, *failedNext;
int **end, *endSize, *endMemory;
} AhoCorasick;
AhoCorasick NewAhoCorasick(int nodeMemory, int alphabetMemory, int endMemoryInit){
AhoCorasick d; int i;
d.nodeMemory=nodeMemory; d.alphabetMemory=alphabetMemory;
d.next = (int**) malloc( nodeMemory*sizeof(int*) );
d.next[0] = (int*) malloc( nodeMemory*alphabetMemory*sizeof(int) );
REP(i,1,nodeMemory) d.next[i] = d.next[i-1] + alphabetMemory;
d.failedNext = (int*) malloc( nodeMemory*sizeof(int) );
d.endSize = (int*) malloc( nodeMemory*sizeof(int) );
d.endMemory = (int*) malloc( nodeMemory*sizeof(int) );
d.end = (int**) malloc( nodeMemory*sizeof(int*) );
rep(i,nodeMemory) d.end[i] = (int*) malloc( endMemoryInit*sizeof(int) );
rep(i,nodeMemory) d.endMemory[i] = endMemoryInit;
return d;
}
void DeleteAhoCorasick(AhoCorasick *d){
int i;
rep(i,d->nodeMemory) free(d->end[i]); free(d->next[0]);
free(d->next); free(d->failedNext); free(d->end); free(d->endSize); free(d->endMemory);
}
void AhoCorasickSetInit(AhoCorasick *d, int alphabetSize){
int i;
d->nodeSize=1; d->alphabetSize=alphabetSize; d->wordSize=0; d->endSize[0]=0;
rep(i,alphabetSize) d->next[0][i]=-1;
}
/* d->endMemory[node] = size とする. */
/* 既に中身に入っている d->end[node][*] はちゃんと保存される */
/* fg=1 なら,d->endMemory[node] >= size の場合無視する. */
void AhoCorasickEndRealloc(AhoCorasick *d, int node, int size, int fg, void *workMemory){
int i, *tmp;
if(fg && d->endMemory[node] >= size) return;
tmp=(int*)workMemory;
rep(i,d->endSize[node]) tmp[i]=d->end[node][i];
free(d->end[node]);
d->end[node] = (int*)malloc( size*sizeof(int) );
rep(i,d->endSize[node]) d->end[node][i] = tmp[i];
d->endMemory[node] = size;
}
void AhoCorasickAddEnd(AhoCorasick *d, int node, int add, void *workMemory){
if(d->endSize[node]==d->endMemory[node]) AhoCorasickEndRealloc(d,node,d->endMemory[node]*2+1,1,workMemory);
d->end[node][d->endSize[node]++] = add;
}
void AhoCorasickAddWord(AhoCorasick *d, int word[], int wordLength, void *workMemory){
int i, j, k, now=0, wn = d->wordSize++;
rep(i,wordLength){
if( d->next[now][word[i]] == -1 ){
k = d->nodeSize++;
d->next[now][word[i]] = k;
d->endSize[k]=0;
rep(j, d->alphabetSize) d->next[k][j] = -1;
}
now = d->next[now][word[i]];
}
AhoCorasickAddEnd(d, now, wn, workMemory);
}
void AhoCorasickConstruct(AhoCorasick *d, void *workMemory){
int i,j,k,now;
int *q, q_st=0, q_size=0;
q = (int*)workMemory; workMemory = (void*)(q+d->nodeSize);
now=0;
rep(k,d->alphabetSize) if(d->next[now][k]!=-1) {
q[q_st+q_size++] = d->next[now][k];
d->failedNext[ d->next[now][k] ] = now;
}
while(q_size){
now = q[q_st++]; q_size--;
rep(k,d->alphabetSize) if(d->next[now][k]!=-1){
i = d->failedNext[now];
while(i){
if( d->next[i][k] != -1 ) break;
i = d->failedNext[i];
}
if(d->next[i][k] != -1) i = d->next[i][k];
d->failedNext[ d->next[now][k] ] = i;
rep(j,d->endSize[i]) AhoCorasickAddEnd(d, d->next[now][k], d->end[i][j], workMemory);
q[q_st+q_size++] = d->next[now][k];
}
}
}
void AhoCorasickSearch(AhoCorasick *d, int str[], int strLength, int res[]){
int i,k,c,m,now=0;
rep(m,d->wordSize)res[m]=0;
rep(i,strLength){
c=str[i];
while(now && d->next[now][c]==-1) now=d->failedNext[now];
if(d->next[now][c]!=-1) now=d->next[now][c];
rep(k,d->endSize[now]) res[ d->end[now][k] ]++;
}
}
void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
int reader(char c[]){int i,s=0;for(;;){mygc(i);if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF) break;}c[s++]=i;for(;;){mygc(i);if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF) break;c[s++]=i;}return s;}
void writer(ll x, char c){int i,sz=0,m=0;char buf[20];if(x<0)m=1,x=-x;while(x)buf[sz++]=x%10,x/=10;if(!sz)buf[sz++]=0;if(m)mypc('-');while(sz--)mypc(buf[sz]+'0');mypc(c);}
int T, N; char A[110000];
char x[801][800]; int len[801];
int arr[110000], as;
int tmp[1000];
int main(){
int i, j, k;
int sum = 0;
ll res;
void *mem = malloc(20000000);
len[0] = 1;
x[0][0] = 1;
REP(i,1,801){
len[i] = len[i-1];
rep(j,len[i]) x[i][j] = x[i-1][j] * 2;
REP(j,1,len[i]) x[i][j] += x[i][j-1]/10, x[i][j-1] %= 10;
if(x[i][len[i]-1] >= 10){
x[i][len[i]] = x[i][len[i]-1] / 10;
x[i][len[i]-1] %= 10;
len[i]++;
}
}
rep(i,801) reverse(x[i], x[i]+len[i]);
rep(i,801) sum += len[i];
AhoCorasick aho = NewAhoCorasick(sum, 10, 100);
AhoCorasickSetInit(&aho, 10);
rep(i,801){
as = 0;
rep(j,len[i]) arr[as++] = x[i][j];
AhoCorasickAddWord(&aho, arr, as, mem);
}
AhoCorasickConstruct(&aho, mem);
reader(&T);
while(T--){
N = reader(A);
as = 0;
rep(i,N) arr[as++] = A[i]-'0';
AhoCorasickSearch(&aho, arr, as, tmp);
res = 0;
rep(i,801) res += tmp[i];
writer(res, '\n');
}
return 0;
}
Current time: 2024年04月24日19時51分47秒
Last modified: 2014年09月23日00時54分28秒 (by laycrs)
Tags: Competitive_Programming HackerRank HackerRank_w4
トップページに戻る
Logged in as: unknown user (not login)