TopCoder SRM 630 Div1 Medium SuffixArrayDiv1

手こずったけど１発回答できてよかった。
http://community.topcoder.com/stat?c=problem_statement&pm=13377

問題

L文字の文字列Sのi番目のsuffix[i]とは、S[i]～S[L-1]で構成されるSの部分文字列である。
ここでsuffix[0]、suffix[1]、…、suffix[L-1]を辞書順ソートしたらsuffix[x]、suffix[y]、suffix[z]…という順になった場合、{x,y,z...}をSuffixArrayという。

ここで、SuffixArrayである数列SA[i]が与えられる。
このSA[i]を生成する文字列のうち、使われている文字の種類を最小化せよ。

解法

最大ケースとして、S[SA[0]]、S[SA[1]]、…に順にa,b,c,....と１個ずつ進んだ異なる文字列を与えれば、明らかにSAを生成できる。
例えばtest caseのSA={3,0,1,2}なら"bcda"は明らかに題意を満たす。

上記のとおりS[SA[i]]とS[SA[i+1]]の関係がS[SA[i]]+1==S[SA[i+1]]なら確実に題意を満たせるが、S[SA[i]]==S[SA[i+1]]でも他の文字次第では題意を満たせる。
S[SA[i]]+1==S[SA[i+1]]ではなくS[SA[i]]==S[SA[i+1]]で済ませられるiが増えれば、その分使える文字列が減るので、S[SA[i]]==S[SA[i+1]]で済ませられるか求めればよい。

まずS[SA[i]]==S[SA[i+1]]とし、i

class SuffixArrayDiv1 {
	public:
	
	int minimalCharacters(vector <int> SA) {
		int i,x,y;
		
		int N=SA.size();
		string S=string(N,127);
		
		S[SA[0]]=0;
		for(i=1;i<N;i++) {
			S[SA[i]]=S[SA[i-1]];
			for(int j=i+1;j<N;j++) S[SA[j]]=S[SA[j-1]]+1;
			int ng=0;
			for(x=0;x<i;x++) for(y=x+1;y<=i;y++) if(S.substr(SA[x])>S.substr(SA[y])) ng=1;
			S[SA[i]]+=ng;
		}
		return S[SA[N-1]]+1;
		
	}
}

まとめ

ABC#009のCが似たような問題で、「ここを欲張って良い解を取ってもどうにかなるなら良い解を取る。ここで欲張ると後が成り立たないならここはあきらめる」というアプローチが有効な問題。