CPSCO2019 Session3 D - Decode RGB Sequence (400)

D - Decode RGB Sequence

概要

押すと押した箇所がRGBという文字列になるスタンプがある。このスタンプを好きな回数押して与えられた文字列が作れるかを判定せよ。ただし、スタンプがはみ出るような押し方はできない。

制約

3 ≦ N ≦ 10^5

方針

難しい。貪欲解は下記の通り。証明できていない。。

• Rで始まりBで終わる
• RBとGGを含まない

解答

Submission #5403036 - CPSCO2019 Session3

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
bool check(string s){
	int n = s.size();
 
	if(s[0] == 'G' || s[0] == 'B') return false;
	if(s[n-1] == 'R' || s[n-1] == 'G') return false;
 
	for(int i = 0; i < n-1; i++){
		if(s.substr(i, 2) == "RB") return false;
		if(s.substr(i, 2) == "GG") return false;
	}
 
	return true;
}
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int N;
	cin >> N;
 
	string S;
	cin >> S;
 
	cout << (check(S) ? "Yes" : "No") << endl;
}