TopCoderOpen 2014 Round2C Easy SubstringReversal

TCOに参加。Easy,Mediumを解いたと思ったけど、Mediumはアルゴリズムも実装もミス。
Challengeではサーバが重く、サーバ応答を待っている間に狙ったミスを先に落とされてしまった。
Easyは何とか通してレートは維持。
http://community.topcoder.com/stat?c=problem_statement&pm=12516

問題

文字列Sが与えられる。
Sの連続した部分領域に対し、文字の並びを反転させるという処理を1回だけ行うことができる。
こうして得られる文字列のうち辞書順最小のものを求めよ。

解法

愚直にやると、領域の左端・右端の選び方がO(N^2)で反転にO(N)かかり、全体でO(N^3)かかってTLEする。

よって、まず最初に左端だけ固定してしまおう。
文字列の各文字を先頭から見ていき、「今見ている文字の後ろに、辞書順で前に来る文字がある」という場合は、今見ている文字とその辞書順で前の文字を両端とした並びの反転が有効である。

このような文字が1個でも見つかった時点で、左端はこの時見ている文字に確定である。
後は右端を総当たりしながら反転・辞書順大小比較を行えばよい。
左端の判定にO(N^2)、その後の右端総当たりと反転でO(N^2)で、合わせてもO(N^2)で処理できる。

class SubstringReversal {
	public:
	int L;
	
	int test(string S) {
		int L=S.size();
		int ret=0,i,j;
		string T=S;
		
		for(i=1;i<L;i++) {
			string T2=S;
			FOR(j,i+1) T2[j]=S[i-j];
			if(T2<T) ret=i,T=T2;
			
		}
		return ret;
	}
	
	vector <int> solve(string S) {
		L=S.size();
		int x,y,r;
		FOR(x,L) {
			for(y=x+1;y<L;y++) {
				if(S[x]>S[y]) {
					vector<int> V;
					r = test(S.substr(x));
					V.push_back(x);
					V.push_back(x+r);
					return V;
				}
			}
		}
		vector<int> V;
		V.push_back(0);
		V.push_back(0);
		return V;
		
	}
}

まとめ

ちょっと迷ったけど最終的には普通に解けてよかった。