上書き処理は逆順から見るといいな～というお気持ちが頭の中に残っていたけど・・・・・

CPSCO2019 Session3 D Decode RGB Sequence

問題概要

長さのマスがすべて白色で塗られている．各マスは左から順に1,2,....,の番号がついている．このマス目内の連続する3 マスに対し、左から順に赤色・緑色・青色に上塗りするスタンプを次々と押していく．つまり，整数iを選んだ時に，マスには赤，マスには緑，マスに青色を塗る．このときすでにスタンプが押されているマスの上にもスタンプを押すことができて、スタンプを押された各マスの色は新たなスタンプの色に上塗りさる。この操作を白色のマスがなくなるまで繰り返し行う．なお，白色のマスがなくなってからも操作の継続はでき，白色のマスがなくなっていれば任意のタイミングで操作を終了できるものとする．この時，文字列sのような色あいが実現できるか判定する．

問題リンク

https://atcoder.jp/contests/cpsco2019-s3/tasks/cpsco2019_s3_d

制約

は'R','G','B'からなる文字列である

考察

• この問題を見たときにこれを思い出した

atcoder.jp

• つまり，逆順に見るというイメージをもってみることにすると良さそうだなということに気がついた
• 1番最後の操作の時点で文字列内に必ず"RGB"の部分は存在しているはずなので，部分文字列"RGB"がない場合は"No"になることが分かった．また，操作時には，"RGB"を上から上書きするので文字列の先頭がRであり，かつ文字列の最後がBでない場合も"No"になることが分かった．
• これ以外は"Yes"だろう・・・・・と思っていた
• ・・・・・・・・・が，甘くなかった．まだ"No"になるケースがあった．
• 実は，"RGB"という文字列を上書きするので，"RB"や"GG"というケースが含まれている場合も"No"になるのだ（これに気が付かずに大量にWAを出してしまった・・・・）
• じゃあ"BR"とか"BG"みたいなのはどうなのかという疑問が生まれる（2文字の部分文字列は上記のものだけではないので）のでこれを検証してみる．実はこれらのケースは"RGB G RGB"，"RGB G RGB"，"RGB B RGB"のケースのみを考えれば問題ないことがわかる．つまり，文字列"RGB"において，RとBが上書きされた状態として存在するのだ．よってこれらの部分文字列が含まれていても良さそうということがわかる．
• 以上を踏まえると以下の条件を満たしていれば"Yes"になることがわかる．

　1.部分文字列"RGB"が含まれている
　2.'R'で始まり'B'で終わっている
　3.部分文字列"RB","GG"を含まないこと

• これを実装すればよい

ソースコード

※マクロは使っていないので無視してください

#include<iostream>
#include<vector>
#include<algorithm>
#include<cctype>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<set>
using namespace std;

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define VSORT(v) sort(v.begin(), v.end());
#define pb(a) push_back(a)


typedef long long ll;

typedef pair<int, int> pii;
typedef pair<ll, ll> pll;


/*************************************************************************/
//多次元配列の確保及び初期化用マクロ
template<typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
	return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template<typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T& t, const V& v) { t = v; }
template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T& t, const V& v) {
	for (auto& e : t) fill_v(e, v);
}
/*************************************************************************/


#define ARRAY_MAX 1000005
const ll INF = 1e9 + 7;
const ll MOD = 1e9 + 7;



int main() {

	ll n;
	string s;
	cin >> n >> s;


	bool ans = true;

	ans &= (s[0] == 'R');
	ans &= (s[n - 1] == 'B');

	if (!ans)
	{
		cout << "No" << endl;
		return 0;
	}

	ans = false;
	for (int i = 0; i <= n - 3; i++)
	{
		if (i <= n - 3)
		{
			if (s[i] == 'R' && s[i + 1] == 'G' && s[i + 2] == 'B')
			{
				ans = true;
			}
		}

		if (i <= n - 2)
		{
			string tmp = s.substr(i, 2);
			if (tmp == "RB" || tmp == "GG")
			{
				ans = false;
				break;
			}
		}
	}

	if (ans)
	{
		cout << "Yes" << endl;
	}
	else
	{
		cout << "No" << endl;
	}
	
	
	return 0;
}