WARush

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

SRM609 Div1 Easy "MagicalStringDiv1"

問題

TopCoder Statistics - Problem Statement

魔法少女のイリーは呪文を唱えるときに"マジカル文字列"を使う。彼女によれば、初め、'>'がkだけ続いた後に、'<'がkだけ続くような文字列X(kは任意の負でない整数)はマジカルであるとのこと。空文字列もマジカル。

イリーは文字列Sを拾った。Sは'<'と'>'の文字からできている。イリーはいくつかの文字をSから取り除いて文字列を変化させることができる。イリーは可能な限り取り除く文字を少なくしてSをマジカル文字列にしたい。

あなたは文字列 S が与えられる。Sから得られる最長のマジカル文字列の長さを返せ。

制約

1 <= Sの文字列長 <= 50


考えたこと

Sのどの場所をマジカル文字列の文字の変わり目('>' から '<' に変わるところ)にするか決め打ちする。その場所までにでてきた'>'の数と、その場所からでてくる'<'の数を数える。その2つの数の小さいほうに合わせて文字を取り除けば、ベストなマジカル文字列ができるので、小さいほうの数 * 2がマジカル文字列の文字列長となる。あとは変わり目の場所を走査して最大値をとる。

ソースコード

class MagicalStringDiv1 {

    public:

    int getLongest(string S) {
        int N = S.size();
        int sum[55];
        memset(sum, 0, sizeof(sum));

        int best = 0;
        for (int m = 0; m < N; m++){
            int cf = 0;
            for (int f = 0; f < m; f++){
                if (S[f] == '>') cf++;
            }
            int ce = 0;
            for (int e = m; e < N; e++){
                if (S[e] == '<') ce++;
            }
            best = max(best, min(cf, ce) * 2);
        }
        return best;
    }
};