保存されている過去のバージョンの一覧

2014年09月23日00時54分28秒

HackerRank Weekly Challenges - Week 4 5問目 - Two Two

Source

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)$ でできる．

C++によるスパゲッティなソースコード

#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月19日14時00分54秒
Last modified: 2014年09月23日00時54分28秒 (by laycrs)
Tags: Competitive_Programming HackerRank HackerRank_w4
トップページに戻る

Logged in as: unknown user (not login)

ログイン：