結果

問題 No.38 赤青白ブロック
ユーザー nmnmnmnmnmnmnmnmnmnmnmnmnmnm
提出日時 2014-10-05 22:07:27
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 301 ms / 5,000 ms
コード長 2,567 bytes
コンパイル時間 757 ms
コンパイル使用メモリ 87,456 KB
実行使用メモリ 4,388 KB
最終ジャッジ日時 2023-08-25 00:51:00
合計ジャッジ時間 9,835 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 282 ms
4,376 KB
testcase_01 AC 248 ms
4,380 KB
testcase_02 AC 246 ms
4,380 KB
testcase_03 AC 263 ms
4,380 KB
testcase_04 AC 263 ms
4,376 KB
testcase_05 AC 301 ms
4,380 KB
testcase_06 AC 254 ms
4,376 KB
testcase_07 AC 252 ms
4,380 KB
testcase_08 AC 298 ms
4,376 KB
testcase_09 AC 268 ms
4,380 KB
testcase_10 AC 287 ms
4,380 KB
testcase_11 AC 286 ms
4,384 KB
testcase_12 AC 262 ms
4,376 KB
testcase_13 AC 285 ms
4,380 KB
testcase_14 AC 269 ms
4,380 KB
testcase_15 AC 285 ms
4,380 KB
testcase_16 AC 233 ms
4,376 KB
testcase_17 AC 253 ms
4,376 KB
testcase_18 AC 288 ms
4,388 KB
testcase_19 AC 267 ms
4,380 KB
testcase_20 AC 265 ms
4,376 KB
testcase_21 AC 245 ms
4,376 KB
testcase_22 AC 260 ms
4,376 KB
testcase_23 AC 289 ms
4,380 KB
testcase_24 AC 251 ms
4,376 KB
testcase_25 AC 276 ms
4,380 KB
testcase_26 AC 265 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

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