まだ全問解いてないけど。
https://beta.atcoder.jp/contests/code-festival-2018-final-open/tasks/code_festival_2018_final_d
問題
N個の文字列S[i]が与えられる。
各文字はアルファベット大文字・小文字のいずれかである。
3文字の文字列のうち、N個の部分文字列として登場回数が最多の物を求めよ。
同着が複数ある場合は、辞書順最小のものを求めよ。
解法
各文字に現れる、3文字の部分文字列を列挙しよう。
しかし愚直にO(|S|^3)かけて列挙すると間に合わない。
幸い、文字の種類がc=52通りしかないので、各位置に対し左右に各文字が登場するか数えていけばO(|S|*c^2)で処理できる。
全体ではO(sum(|S|)*c^2 + c^3)なので割と大きいが何とか間に合う。
int N; string A[303030]; string M; int L[90909][53]; int R[90909][53]; int ret[52][52][52]; int pat[52][52][52]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; int ma=0; FOR(i,N) { cin>>A[i]; FORR(c,A[i]) { if(c>='A' && c<='Z') c-='A'; else c=c-'a'+26; } FOR(j,52) FOR(x,A[i].size()+2) L[x][j]=R[x][j]=0; FOR(j,A[i].size()) { FOR(x,52) L[j+1][x]=L[j][x]; L[j+1][A[i][j]]++; } for(j=A[i].size()-1;j>=0;j--) { FOR(x,52) R[j+1][x]=R[j+2][x]; R[j+1][A[i][j]]++; FOR(x,52) FOR(y,52) if(L[j][x]&&R[j+2][y]) { if(pat[x][A[i][j]][y]==0) { pat[x][A[i][j]][y]=1; ret[x][A[i][j]][y]++; ma=max(ma,ret[x][A[i][j]][y]); } } } FOR(j,A[i].size()) { FOR(x,52) FOR(y,52) if(L[j][x]&&R[j+2][y]) pat[x][A[i][j]][y]=0; } } FOR(i,26) M+=(char)('A'+i); FOR(i,26) M+=(char)('a'+i); FOR(i,52) FOR(j,52) FOR(x,52) if(ret[i][j][x]==ma) { cout<<M[i]<<M[j]<<M[x]<<endl; return; } }
まとめ
もうちょい計算量落ちないかな。