結果

問題 No.38 赤青白ブロック
ユーザー nmnmnmnmnmnmnmnmnmnmnmnmnmnm
提出日時 2014-10-05 22:07:27
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 281 ms / 5,000 ms
コード長 2,567 bytes
コンパイル時間 825 ms
コンパイル使用メモリ 88,416 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-12-23 12:34:14
合計ジャッジ時間 8,791 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

/*
解説
赤と青のブロックが合計20個なので、
抜く場合の2^20通りをすべて試す全探索です。
白を抜かずに赤と青だけ抜く、
というのがこの問題の難しいところのつもり。
動的計画法でも解けそうな気もしますが、
もし動的計画法でできるなら解法を知りたいです。

Test Cases
1.txt
25 16
WWRWWWBRRWBBWBBRRBRBWRRWRRBBBW
28
2.txt
6 3
WRRBBWBRRRWWBBBBBWRWWBWRRRBWWR
23
3.txt
12 12
WBBRWRWWRRBWWWRBBWRWBBBRWRBRRB
27
4.txt
15 2
RRBRRWBBWWRBBRRWBWRRBWWBBWRWBW
28
5.txt
21 4
RRBBWBWWBBRRBRWBRRRRRWWWBBBWWW
29
6.txt
24 23
RBWBBWBWRBRRRWBBRWWWBBBRRRWWWR
29
7.txt
14 1
RBBWBRBWWRWWRWBWWRRRBWBWRBRRBB
26
8.txt
4 15
RBBWRWBWRRBWBBWRWRRWRWBWBBWRBR
27
9.txt
23 29
RBRBWRRWWRBRWBBWRBWWRWRBWRWBBB
29
10.txt
29 2
RRWBWBWRWWWBRRWWBRBBRWBRBBBWRR
26
*/

#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
 
using namespace std;
 
#define sz size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(c) (c).begin(), (c).end()
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define clr(a, b) memset((a), (b) ,sizeof(a))
 
#define MOD 1000000007
 
#define N 30
 
int main(){
    int kr,kb;
    cin >> kr >> kb;
    string s;
    cin >> s;
    int ans = 0;
    int mask = 0;
    rep(i,0,N){
        if(s[i] == 'W'){
            mask |= (1<<i);
        }
    }
    for(int i = mask; i < (1<<N); i = (i+1)|mask){
        string s1 = "WWWWWWWWWWWWWWWWWWWWWWWWWWWWWW";
        rep(j,0,N){
            if(((mask>>j)&1)==1){
                s1 += 'W';
            }
            else{
                if(((i>>j)&1) == 1){
                    s1 += s[j];
                }
            }
        }
        s1 += "WWWWWWWWWWWWWWWWWWWWWWWWWWWWWW";
        int flag = 1;
        rep(j,N,N*2){
            if(s1[j] == 'R'){
                if(s1[j-kr] == 'R' || s1[j+kr] == 'R'){
                    flag = 0;
                    break;
                }
            }
            else if(s1[j] == 'B'){
                if(s1[j-kb] == 'B' || s1[j+kb] == 'B'){
                    flag = 0;
                    break;
                }
            }
        }
        if(flag == 1){
            ans = max(ans,int(s1.sz)-2*N);
        }
    }
    cout << ans << endl;
	return 0;
}
0