kmjp's blog

競技プログラミング参加記です

TopCoder SRM 779 : Div1 Medium SubstringQueries

なんとか通ってよかった。
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取れてよかった。