No.38 赤青白ブロック - yukicoder
- 自力でとけなかった。計算量見積もりがまだまだちゃんとできてない。
- Kr 個となりが同じ色かの判定で変なフラグ管理をしようとして WA になってしまった。一発で通せるようにりたいなぁ。
- 再帰をうまく使うともっと効率のよい枝刈りができるんだろうけど、とりあえずこれで。
class RedBlueWhiteBlocks {
public:
void solve(void) {
int Kr,Kb;
cin>>Kr>>Kb;
string S;
cin>>S;
int N = S.length();
vector<int> ri;
vector<int> bi;
REP(i, N)
{
if (S[i] == 'R')
ri.push_back(i);
else if (S[i] == 'B')
bi.push_back(i);
}
assert(ri.size()==10);
assert(bi.size()==10);
vector<int> badr;
vector<int> badb;
int maxLen = 0;
for (int r = 0; r < (1<<10); ++r)
for (int b = 0; b < (1<<10); ++b)
{
string tmp(S);
REP(i,10)
{
if (r & (1<<i))
tmp[ri[i]] = ' ';
if (b & (1<<i))
tmp[bi[i]] = ' ';
}
tmp.erase (remove(RANGE(tmp), ' '), tmp.end());
if (maxLen > (int)tmp.length())
continue;
bool ok = true;
int n = tmp.size();
REP(i,n)
{
if ( (tmp[i] == 'R' && i-Kr >= 0 && tmp[i-Kr] == 'R') ||
(tmp[i] == 'B' && i-Kb >= 0 && tmp[i-Kb] == 'B') )
{
ok = false;
break;
}
}
if (ok)
maxLen = max(maxLen, n);
}
cout<<maxLen<<endl;
}
};