なんとか通ってよかった。
https://community.topcoder.com/stat?c=problem_statement&pm=15740&rd=17848&rm=333558&cr=40125327
問題
文字列Sをk回並べた文字列Tを考える。
x∈[1,|T|]の各xにおいて、f(x)をTの部分文字列のうち長さxのものの中で、辞書順最小のもののindexとする(タイなら最小のindexを取る)。
f(x)の総和を求めよ。
解法
k=1と2以上で分ける。
k=1の場合
各indexから始めた部分文字列において、長さを1~|T|までだんだん長くしつつ、それぞれを辞書順に並べたときの昇順にindexをソートしていこう。
長さがxの時、indexは|S|-x以下のものしか取れないので、それを超えるものは適宜消していく。
愚直にsubstringを大小比較するとO(|S|^3)かかってTLEするので注意。
k>=2の場合
長さが|S|以下の場合と|T|-|S|より大きい場合は個別に対応する。
それ以外の場合、結局indexを0~(|S|-1)から始めたときの長さ|S|の部分文字列を比較すれば、f(x)はその場合の辞書順最小文字列を構築するindexとなる。
長さが|S|以下のケースは上のk=1のケースと同じように行う(ただし「indexは|S|-x以下のものしか取れない」の制限はない)
一方|T|-|S|より大きい場合は「indexは|S|-x以下のものしか取れない」の代わりに「indexは|T|-x以下のものしか取れない」と読み替えて処理すればよい。
class SubstringQueries { public: long long solve(string S, int k) { int N=S.size(); ll ret=0; vector<int> cand[2525]; int i; S+=S; if(k==1) { vector<vector<int>> V; V.resize(1); FOR(i,N) V[0].push_back(i); for(int len=1;len<=N;len++) { vector<vector<int>> D; int mi=-1; FORR(W,V) { vector<int> C[26]; FORR(v,W) { C[S[v+len-1]-'a'].push_back(v); } FOR(i,26) if(C[i].size()) { if(mi==-1) mi=C[i][0]; if(C[i].back()+len>=N) C[i].pop_back(); if(C[i].size()) D.push_back(C[i]); } } ret+=mi; swap(V,D); } } else { FOR(i,N) cand[0].push_back(i); for(int len=1;len<=N;len++) { char m='z'+1; FORR(i,cand[len-1]) { if(S[i+len-1]<m) { m=S[i+len-1]; cand[len].clear(); } if(S[i+len-1]==m) cand[len].push_back(i); } ret+=cand[len][0]; } ret+=1LL*N*(k-2)*cand[N][0]; int pre=0; for(int cur=1;cur<N;cur++) { int len=2*N-cur; if(S.substr(pre,len)>S.substr(cur,len)) { pre=cur; } ret+=pre; } } return ret; } }
まとめ
2Chal取れてよかった。