SRM606 Div2 Easy "EllysSubstringSorter"
問題
TopCoder Statistics - Problem Statement
訳
エリーは大文字のアルファベットでのみ構成された文字列Sと、文字列を更新する魔法の装置を持っていた。その装置の強度はLである。
装置は次のようなものだ。0 <= i <= length(S) - Lのようなiを、装置に入力することができる。すると、S[i]からS[i + L]までを、アルファベット順にソートされる。
例えば、S="TOPCODER"、L=4だとする。装置に対し、i=0を入力すると、ソート対象となる部分文字列は"TOPC"となる。それは"COPT"とソートされる。残りの部分文字列である("....ODER")に変化はない。よって、結果は"COPTODER"となる。i=2を入力すると"TOCDOPER"となる。これは"PCOD"が"CDOP"で置き換えられ、"TO....ER"は変化しないためだ。
エリーの魔法の装置は、使うと自爆するため、一回しか使えない。あなたは上記に出てくる文字列Sと整数Lが与えられる。エリーがこの装置を1回使用して得られる辞書順でもっとも小さい文字列を返せ。
制約
2 <= L <= 50
L <= Sの長さ <= 50
考えたこと
実際にシミュレートして比べていく。
c++ では文字列の辞書順の比較は s1 < s2など、intと同じようにできる。
ソースコード
class EllysSubstringSorter { public: string getMin(string S, int L) { string res = "ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ"; int N = S.size(); // iを一通りやる for (int i = 0; i <= N - L; i++) { string T = S; // ソート while (true){ bool update = false; for (int j = 0; j < L - 1; j++) { int p = i + j; if (T[p + 1] < T[p]) { char t = T[p]; T[p] = T[p + 1]; T[p + 1] = t; update = true; } } if (!update) break; } if (T < res) res = T; } return res; } };