HackerRank 101 Hack June'14 4問目
problem statement(コンテストページ)
problem statement
$N$ 文字のアルファベット小文字のみからなる文字列 $S$ が与えられる.
$S$ の部分文字列を辞書順で小さい方から全て繋げた文字列を $T$ とする.
$T$ の $K$ 番目の文字を求める問題.
Suffix ArrayとLongest Common Prefixを求めておく.
SAの最初の部分文字列から見ていくと,それを始点とする,今まで処理していない,部分文字列の数,および,その総文字数は(部分文字列の位置,および,LCPから)簡単に求められる.
また,処理していく順番が部分文字列において,辞書順で小さい方から見ていくことになる.
よって,順番になぞっていって,どこが開始地点かを調べ,どの部分文字列化を調べ,その何文字目かを調べれば良い.
#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
void llIntSort(ll d[],int m[],int s){int i,j,a;ll k,t;if(s<=1)return;k=(d[0]+d[s-1])/2;i=-1;j=s;for(;;){while(d[++i]<k);while(d[--j]>k);if(i>=j)break;t=d[i];d[i]=d[j];d[j]=t;a=m[i];m[i]=m[j];m[j]=a;}llIntSort(d,m,i);llIntSort(d+j+1,m+j+1,s-j-1);}
void charCreateSuffixArray(char t[], int n, int res[], void *WorkMemory) {
int i, h, *g, *b; ll *d;
g = (int*)WorkMemory; WorkMemory = (void*)(g+n+1);
b = (int*)WorkMemory; WorkMemory = (void*)(b+n+1);
d = (ll*) WorkMemory;
rep(i,n+1) res[i] = i, d[i] = g[i] = t[i];
b[0] = 0; b[n] = 0;
llIntSort(d,res,n+1);
for(h=1;b[n]!=n;h*=2){
rep(i,n+1){
d[i] = g[res[i]] * (1LL<<32);
if(res[i]+h<n+1) d[i] += g[res[i]+h];
}
llIntSort(d,res,n+1);
rep(i,n){ b[i+1]=b[i]; if(g[res[i]]!=g[res[i+1]]||g[res[i]+h]!=g[res[i+1]+h]) b[i+1]++; }
rep(i,n+1) g[res[i]]=b[i];
}
}
/* Kasai-Lee-Arimura-Arikawa-Park: O(n) */
void charCreateLCPFromSA(char *t, int n, int *SA, int *res, void *WorkMemory) {
int i, j, h=0, *b;
b = (int*)WorkMemory;
rep(i,n+1) b[SA[i]]=i;
rep(i,n+1){
if(b[i]){
for(j=SA[b[i]-1];j+h<n&&i+h<n&&t[j+h]==t[i+h];h++);
res[b[i]]=h;
}else res[b[i]] = -1;
if(h>0)h--;
}
}
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);}
void reader(ll *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(const char c[]){int i;for(i=0;c[i]!='\0';i++)mypc(c[i]);}
int T, N;
char S[200000];
ll K;
int SA[200000], LCP[200000];
int mem[2000000];
char res[10];
int main(){
int i, j;
ll len, all;
ll KK;
scanf("%d",&T);
while(T--){
scanf("%s",S);
N = strlen(S);
scanf("%lld",&K);
K--;
assert(K>=0);
rep(i,N) assert('a'<=S[i] && S[i]<='z');
charCreateSuffixArray(S, N, SA, mem);
charCreateLCPFromSA(S, N, SA, LCP, mem);
res[0] = 0;
REP(i,1,N+1){
len = N - SA[i];
all = len * (len+1) / 2 - ((ll)LCP[i] * (LCP[i]+1)) / 2;
if(K >= all){ K -= all; continue; }
REP(j,LCP[i],len){
if(K >= j+1){ K -= j+1; continue; }
res[0] = S[SA[i]+K];
break;
}
assert(j<len);
break;
}
printf("%c\n",res[0]);
}
return 0;
}
Current time: 2024年03月28日19時48分40秒
Last modified: 2014年09月23日01時14分57秒 (by laycrs)
Tags: Competitive_Programming HackerRank HackerRank_101jun14
トップページに戻る
Logged in as: unknown user (not login)