急遽★3になった問題。
http://yukicoder.me/problems/31
問題
'R','B','W'が10個ずつで構成された30文字の文字列Sがある。
ここからいくつか'R''B'を取り除き、
- 'R'の左右Kr個離れた位置に'R'があってはならない
- 'B'の左右Kb個離れた位置に'B'があってはならない
という条件を満たす文字列を生成したい。
条件を満たす最長の文字列を答えよ。
解法
取り除く候補は20文字なので、2^20通り総当たりして条件を満たすかチェックすればよい。
int KR,KB; string S; int ms[31]; void solve() { int i,j,k,l,r,x,y; string s; cin>>KR>>KB>>S; j=0; FOR(i,30) { if(S[i]=='W') ms[i]=21; else ms[i]=j++; } int ma=0; FOR(i,1<<20) { string T; int ok=1; FOR(j,30) if((i&(1<<ms[j]))==0) { T+=S[j]; if(S[j]=='R' && T.size()>KR && T[T.size()-KR-1]=='R') ok=0; if(S[j]=='B' && T.size()>KB && T[T.size()-KB-1]=='B') ok=0; } if(ok) ma=max(ma,(int)T.size()); } cout<<ma<<endl; }
まとめ
枝…刈り?