TopCoderOpen 2014 Round1A Easy EllysSortingTrimmer

TCO R1Aに参加。ただし直前のレートが良かったためbye扱いなのでParallel Round参加。
結果的にはまさかの3完Room Leaderだったので、通常参加していた方がよかった…。
http://community.topcoder.com/stat?c=problem_statement&pm=12971

問題

文字列Sと数値Lが与えられる。
この文字に対し、「連続するL字を選択してその部分だけソートし、かつL字より後の部分を削除する」という処理を任意回数実行できるとき、Sから生成できる辞書順最小の文字列を答えよ。

解法

本番はSから生成できる文字列を全部列挙した。
文字列の種類がO(N^2)で、setを使った管理がO(logN)、処理対象のL字の選択方法をO(N)なので全体でO(N^3 logN)で済む。

実際はもっとシンプルな方法で解ける。
以下どちらでも良いが、以下のコードは前者。

• 後ろから順にL文字選択してソートする、ということをだんだん前に向けて行い、最終的に先頭L文字を取る。
  • この操作により文字列中後ろの方にある辞書順で前にある文字を文字列中の前に移動できる。
• 先頭1文字と、あと残りの文字列全部を辞書順ソートした(L-1)文字を合わせて再度ソート。
  • 2文字以降は処理の過程で削除出来るが、1文字目だけは削除できないため。

以下コメント内は本番書いた全列挙コード。

class EllysSortingTrimmer {
	public:
	string getMin(string S, int L) {
		int i;
		for(i=S.size()-L;i>=0;i--) sort(S.begin()+i,S.begin()+i+L);
		return S.substr(0,L);
		/*
		set<string> SS,SS2,SS3;
		int i;
		SS.insert(S);
		SS2.insert(S);
		while(!SS2.empty()) {
			SS3.clear();
			ITR(it,SS2) {
				FOR(i,it->size()-L+1) {
					string nn=it->substr(0,i+L);
					sort(nn.begin()+i,nn.begin()+i+L);
					if(SS.find(nn)==SS.end()) {
						SS3.insert(nn);
						SS.insert(nn);
					}
				}
			}
			SS2=SS3;
		}
		return *SS.begin();
		*/
	}
};

まとめ

最大文字列長が50だったので全列挙で間に合ったけど、2500とかだったら無理だったな。