Yukicoder038 赤青白ブロック

問題概要

“R”,“B”,“W”のブロックが並んでいる。 次の条件を満たすように”R”,“B”のブロックを削除するが、残るブロックを最大化したい。 あるブロックが”R”のとき、左右$Kr$個目のブロックは”R”であってはならない。 あるブロックが”B”のとき、左右$Kb$個目のブロックは”B”であってはならない。

$1<=Kr,Kb<=29$、$|S|≦30$、各色は10個ずつ

yukicoder

解法

“R”,“B”のブロックについて、これらそれぞれについて使うかどうかを$2^{20}$通り全部試せば良い。

計算量:$O(2^{|R|+|B|})$

ソース

    #include <bits/stdc++.h>
    using namespace std;
    
    #define SZ(a) int((a).size())
    #define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
    
    int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
    
        int Kr, Kb; cin >> Kr >> Kb;
        string s; cin >> s;
    
        int ans = 0;
        FOR(r, 0, 1 << 10) {
            FOR(b, 0, 1 << 10) {
    
                string t;
                int rmask = 0, bmask = 0;
                int rc = 0, bc = 0;
                FOR(i, 0, 10) {
                    if (r&(1 << i)) {
                        rmask |= 1 << i;
                    }
                    if (b&(1 << i)) {
                        bmask |= 1 << i;
                    }
                }
                FOR(i, 0, SZ(s)) {
                    if (s[i] == 'R') {
                        if (rmask & (1 << rc))t += s[i];
                        rc++;
                    }
                    else if (s[i] == 'B') {
                        if (bmask & (1 << bc))t += s[i];
                        bc++;
                    }
                    else {
                        t += s[i];
                    }
                }
                int ok = 1;
                FOR(i, 0, SZ(t)) {
                    if (t[i] == 'R') {
                        if (i - Kr >= 0 && t[i - Kr] == 'R')ok = 0;
                        if (i + Kr < SZ(t) && t[i + Kr] == 'R')ok = 0;
                    }
                    else if (t[i] == 'B') {
                        if (i - Kb >= 0 && t[i - Kb] == 'B')ok = 0;
                        if (i + Kb < SZ(t) && t[i + Kb] == 'B')ok = 0;
                    }
                }
                if (ok) {
                    ans = max(ans, SZ(t));
                }
            }
        }
    
        cout << ans << "\n";
    
        return 0;
    }