SRM609は出られない予定だったが、急遽出られることに。
今回はEasy・Mediumがえらく簡単だった回。225pt/450ptでもいいんじゃないかというぐらい。
自分はEasyはサクサク解けたけどMediumでちょっと手こずった。
ともあれEasy/Mediumを解けてレートが微増。
http://community.topcoder.com/stat?c=problem_statement&pm=13003
問題
'>' '<' だけで構成された文字列がある。
ここからいくつかの文字を取り除き、'>'がいくつか連続した後に同数の'<'が来るようにしたい。
条件を満たす最長の文字列長を求めよ。
解法
いろんなやり方がある。
自分は、文字列を前から見て途中まで'>'を拾い、残りは'<'を拾うようにして少ない方に数を合わせる、という手法で対応。
'>'を拾い終える位置を総当たりで変えることでO(L^2)で解答。
class MagicalStringDiv1 { int L; public: int getLongest(string S) { int i,x,r=0; L=S.size(); for(i=-1;i<L+3;i++) { int a=0,b=0; FOR(x,L) { if(x<i && S[x]=='>') a++; if(x>=i && S[x]=='<') b++; } r=max(r,2*min(a,b)); } return r; } };
まとめ
これはDiv2 Easyか225ptでいいのでは…。