結果

問題 No.38 赤青白ブロック
ユーザー IL_mstaIL_msta
提出日時 2015-06-30 07:11:58
言語 C++11
(gcc 11.4.0)
結果
MLE  
実行時間 -
コード長 2,338 bytes
コンパイル時間 717 ms
コンパイル使用メモリ 91,468 KB
実行使用メモリ 817,936 KB
最終ジャッジ日時 2024-07-07 21:22:21
合計ジャッジ時間 4,045 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 MLE -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define _USE_MATH_DEFINES

#include <iostream>
#include <iomanip>

#include <algorithm>
#include <cmath>

#include <string>
#include <list>
#include <queue>
#include <vector>
#include <complex>
#include <set>

/////////
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define P(p) cout<<(p)<<endl;
/////////
typedef long long LL;
typedef long double LD;
/////////
using namespace::std;
/////////
int Kr,Kb;
bool che(string s){
	//0-29
	int Len = s.size();
	for(int i=0;i<Len;++i){
		if(s[i]=='R'){
			if(i+Kr<Len){
				if( s[i+Kr] == 'R'){
					return false;
				}
			}
		}else if(s[i]=='B'){
			if(i+Kb<Len){
				if( s[i+Kb] == 'B'){
					return false;
				}
			}
		}
	}
	return true;
}

int solve(string s){
	if(che(s) ==true){
		return s.size();
	}
	int ans  = 0;
	int tans = 0;
	string temp;
	for(int i=0;i<s.size();++i){
		if(s[i] == 'R'){
			if( (i+Kr<s.size() && s[i+Kr]=='R') ||
				(i-Kr>=0 && s[i-Kr]=='R')
			)
			{
				temp = s;
				//s[i]を抜いた文字
				tans = solve( temp.replace(i,1,"") );
				if(ans < tans){
					ans = tans;
				}
			}
		}
		else if(s[i] == 'B'){
			if( (i+Kb<s.size() && s[i+Kb]=='B') ||
				(i-Kb>=0 && s[i-Kb]=='B')
			)
			{
				temp = s;
				//s[i]を抜いた文字
				tans = solve( temp.replace(i,1,"") );
				if(ans < tans){
					ans = tans;
				}
			}
		}
	}
	return ans;
}
int main(void){
    std::cin.tie(0); 
    std::ios::sync_with_stdio(false);
    std::cout << std::fixed;//
    //cout << setprecision(6);//
	
	cin>>Kr>>Kb;
	string str;
	cin>>str;
	int ans = 10;

	//ans = solve(str);

	if(Kr == 1){
		for(int i=0;i<str.size()-1;++i){
			if(str[i]=='R'&&str[i+1]=='R'){
				str.replace(i,1,"");
				--i;
			}
		}
	}
	if(Kb == 1){
		for(int i=0;i<str.size()-1;++i){
			if(str[i]=='B'&&str[i+1]=='B'){
				str.replace(i,1,"");
				--i;
			}
		}
	}

	if( che(str) == true ){
		P(str.size());
		return 0;
	}

	queue<string> que;
	string itStr,tempStr;
	que.push(str);

	int tans;
	while( !que.empty() ){
		itStr = que.front();
		que.pop();
		if( itStr.size() > ans+1 ){
			for(int i=0;i<itStr.size();++i){
				if(itStr[i] != 'W'){
					tempStr = itStr;
					tempStr.replace(i,1,"");
					if( che(tempStr) != true ){
						que.push(tempStr);
					}else{
						tans = tempStr.size();
						ans = max(ans,tans);
					}
				}
			}
		}
	}


	P(ans);
	return 0;
}
0