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