結果

問題 No.38 赤青白ブロック
ユーザー IL_mstaIL_msta
提出日時 2015-06-30 07:47:14
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 6 ms / 5,000 ms
コード長 2,525 bytes
コンパイル時間 1,096 ms
コンパイル使用メモリ 97,772 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-06 02:06:31
合計ジャッジ時間 1,664 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

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 = 12;//RBW10

	//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);
	set<string> strSet;
	bool flag = strSet.insert(str).second;

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


	P(ans);
	return 0;
}
0