WARush

SRMの結果とか、解けた問題のコードを書いていきます

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;
    }
};