ABC102 D Equal Cut とりあえず真ん中を固定してみる

2019 競プロ AtCoder 600 二分探索 累積系 尺取り バグる系 真ん中を固定

ABC102 D Equal Cut

問題概要

リンク参照

問題リンク

https://atcoder.jp/contests/abc102/tasks/arc100_b

考察

  • 真ん中を固定してみたくなります（典型っぽい）
  • PとQ，RとSについては同じくらいの値になっていれば良さそうに感じます（まぁ分からんでもない）
  • 同じくらいの値になる境界を探す処理が必要になります→これは累積和を取って尺取りor二分探索すれば良さそう
  • 実装します
  • とてもバグります(´；ω；`)ｳｯ…
  • 非常に🌲びしい

ソースコード

#include<iostream>
#include<vector>
#include<algorithm>
#include<cctype>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<set>

#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 SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)

using namespace std;

typedef long long int 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 100005
const ll INF = 1e9;
const ll MOD = 1e9 + 7;

int dx[4] = { 1,0,0,-1 };
int dy[4] = { 0,1,-1,0 };




/******************************************************************************************/

ll sum[200005];


int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}

	for (int i = 1; i <= n; i++)
	{
		sum[i] = sum[i - 1] + a[i - 1];
	}
	
	ll ans = 1LL << 60;


	int left = 1, center = 2,right = 3;
	while(center < n - 1)
	{

		while (left < center) {
			if (abs(sum[left] - (sum[center] - sum[left])) > abs(sum[left + 1] - (sum[center] - sum[left + 1]))) {
				left++;
			}
			else
			{
				break;
			}
		}
		
		while (right < n) {
			if (abs(sum[n] - sum[right] - (sum[right] - sum[center])) > abs(sum[n] - sum[right + 1] - (sum[right + 1] - sum[center]))) {
				right++;
			}
			else
			{
				break;
			}
		}

		ll mini = min(min(sum[left], sum[center] - sum[left]), min(sum[right] - sum[center], sum[n] - sum[right]));
		ll maxi = max(max(sum[left], sum[center] - sum[left]), max(sum[right] - sum[center], sum[n] - sum[right]));
		ans = min(ans, maxi - mini);
		center++;
	}

	cout << ans << endl;


	return 0;
}

01BFSが使える

2019 競プロ AtCoder ABC005 グラフ BFS 01BFS

ABC005 C 器物損壊！高橋君

問題概要

リンク参照

問題リンク

https://atcoder.jp/contests/arc005/tasks/arc005_3

考察

  • 壁が来た時には壊して進むことが考えられるので今まで何回壁を壊したのかの情報を持っておきたい
  • なるべく壁を壊す回数を少なくして進む方がよさそう
  • 壁を壊して進むことは，コスト1の移動に相当し，壁以外を進む場合はコスト0の移動と考えると01BFSが使える
  • これを実装して投げたら通った(・∀・)

ソースコード

#include<iostream>
#include<vector>
#include<algorithm>
#include<cctype>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#include<climits>

#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 SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)

using namespace std;


typedef long long int 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 100005
const int INF = INT32_MAX / 3;
const ll MOD = 1e9 + 7;

int dx[4] = { 1,0,0,-1 };
int dy[4] = { 0,1,-1,0 };


int ans[550][550];
char mp[550][550];
int h, w;
int sy, sx, gy, gx;

int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

		

	for (int i = 0; i < 550; i++)
	{
		for (int j = 0; j < 550; j++)
		{
			ans[i][j] = INF;
		}
	}


	cin >> h >> w;


	for (int i = 0; i < h; i++)
	{
		for (int j = 0; j < w; j++)
		{
			cin >> mp[i][j];
			if (mp[i][j] == 's') {
				sy = i;
				sx = j;
			}
			if (mp[i][j] == 'g') {
				gy = i;
				gx = j;
			}
		}
	}

	

	deque<pii> que;

	que.push_back(pii(sy,sx));
	ans[sy][sx] = 0;

	while (!que.empty())
	{
		pii now = que.front();
		que.pop_front();
		
		for (int i = 0; i < 4; i++)
		{
			int ny = now.first + dy[i];
			int nx = now.second + dx[i];

			
			//範囲内
			int cost = 0;

			if (0 <= ny && ny < h && 0 <= nx && nx < w) {

				if (mp[ny][nx] == '#') {
					//壁なら破壊コストがいる
					cost = 1;
				}
				else
				{
					cost = 0;
				}

				//コストの更新

				if (ans[ny][nx] > ans[now.first][now.second] + cost) {
					ans[ny][nx] = ans[now.first][now.second] + cost;
					if (cost == 0) {
						que.push_front(pii(ny, nx));
					}
					else
					{
						que.push_back(pii(ny, nx));
					}

				}
			}
		}
	}


	if (ans[gy][gx] < 3) {
		cout << "YES" << endl;
	}
	else
	{
		cout << "NO" << endl;
	}
	
	return 0;
}

The 高校数学（組み合わせ）

2019 競プロ AtCoder ABC132 数学 組み合わせ 重複組み合わせ

ABC132 D Blue and Red Balls

問題概要

K個の青ボールとN-K個の赤いボールが与えられる．これらのボールを一列に並べる．１回の操作で連続する青いボールは何個でも回収できる．この時，K個の青いボールを全て回収するのにi回操作を行う並べ方は何通りあるか，その答えを10^9+7で割った余りを求めよ

問題リンク

https://atcoder.jp/contests/abc132/tasks/abc132_d

制約

1\leq N \leq K \leq 2000


考察

  • 高校数学の組み合わせ感があるので考える
  • i回操作しないといけないということは，青いボールをi個に分断してある必要がある．この組み合わせは，青いボールの間の個数K-1箇所の中からi-1箇所選ぶ組み合わせになるので _{K-1} \mathrm{C} _{i-1}通り
  • これを赤ボールの間の個数N-K-1と両端の2か所の合計N-K+1箇所からi箇所選んで埋め込めばいいので，この組み合わせは _{N-K+1} \mathrm{C} _{i}通り
  • 青いボールの分断の仕方 _{K-1} \mathrm{C} _{i-1}通りに対して埋め込み方が _{N-K+1} \mathrm{C} _{i}通りあるので，i回の操作で青ボールを全て取りきることができる並べ方は _{K-1} \mathrm{C} _{i-1} \times _{N-K+1} \mathrm{C} _{i}通りとなるので各iについてこれを計算すればよい

ソースコード

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

#include<iostream>
#include<vector>
#include<algorithm>
#include<cctype>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<set>

#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 SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)

using namespace std;

typedef long long int 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 100005
const ll INF = 1e9 + 7;
const ll MOD = 1e9 + 7;

int dx[4] = { 1,0,0,-1 };
int dy[4] = { 0,1,-1,0 };


struct Combination {

	vector<ll> fact, rfact;

	Combination(ll sz) : fact(sz + 1), rfact(sz + 1) {

		fact[0] = 1;
		for (ll i = 1; i < fact.size(); i++) {
			fact[i] = fact[i - 1] * i % MOD;
		}
		//逆元
		rfact[sz] = inv(fact[sz]);
		for (ll i = sz - 1; i >= 0; i--) {
			rfact[i] = rfact[i + 1] * (i + 1) % MOD;
		}
	}

	ll inv(ll x) {
		//modpow
		return pow(x, MOD - 2);
	}
	ll pow(ll x, ll n) {
		//累乗
		ll ret = 1;
		while (n > 0) {
			if (n & 1) (ret *= x) %= MOD;
			(x *= x) %= MOD;
			n >>= 1;
		}
		return (ret);
	}
	ll P(ll n, ll r) {
		//順列
		if (r < 0 || n < r) return (0);
		return (fact[n] * rfact[n - r] % MOD);
	}

	ll C(ll p, ll q) {
		//組み合わせ
		if (q < 0 || p < q) return (0);
		return (fact[p] * rfact[q] % MOD * rfact[p - q] % MOD);
	}

	ll H(ll n, ll r) {
		//重複組み合わせ
		if (n < 0 || r < 0) return (0);
		return (r == 0 ? 1 : C(n + r - 1, r));
	}
};


/******************************************************************************************/



int main() {

	ll n, k;
	cin >> n >> k;
	ll red = n - k;
	ll inside = k - 1;

	Combination comb(2050);


	for (ll i = 1; i <= k; i++)
	{
		cout << comb.C(k - 1, i - 1)*comb.C(n - k + 1, i) % MOD << endl;

	}

	return 0;
}

累積XORだけど生えなかった・・・・(´；ω；`)ｳｯ…

競プロ 文字列 Codeforces Round571 div2 累積系 累積XOR

Codeforces Round #571(Div. 2) C Vus the Cossack String

問題概要

２進数の文字列aとbが与えられる．文字列aの連続する部分文字列で，文字列bと同じ長さのものと文字列bを比較する．この時，文字が異なる位置が偶数個存在する文字列aの連続する部分文字列の個数を求める．

問題リンク

https://codeforces.com/contest/1186/problem/C

制約

1\leq |a| \leq 10^{6}
1\leq |b| \leq |a|
文字列aとbは２進数の文字列

考察

  • 愚直解から計算量を落とそうといろいろ考えたけどダメだった・・・・
  • 累積系の処理をしておくと良さそうな感じはしたけどそこから何も見えてこなかった（おいおい・・・・）
  • （Twitterで累積XORの解法を観測・・・）累積XORをとると何が分かるのか？？？・・・・・部分文字列の中にある1の個数の奇偶が分かるな～
  • aの部分文字列と文字列bの各bitを比較して違ったら+1して，最後にこれらが偶数なら解に含まれるというのが愚直な方法になる．bitが違ったら+1になる・・・・bitが同じ場合は無視・・・・・これに該当する演算は・・・・・XORならbitが違う場合は1になる・・・・・これか・・・・・(´；ω；`)ｳｯ…
  • 各ビットのXORを取って1になっている部分の個数を数えて偶数になる・・・・これらのXORも0になる感じでは？？・・・・・結局全部XOR取った時に0であればいいのか・・・・？
  • 文字列a部分文字列とbの全部のXORが0でなんやねん・・・・（ここでサンプルをグッとにらむ）・・・どうやら文字列a部分文字列とbに含まれる1の個数の奇偶が同じなら良さそう・・・・・・
  • 結局1の個数の奇偶で判定できるのか・・・・ならば文字列a部分文字列は累積XORで1の個数の奇偶を求めれば良さそうだし，文字列bについては固定なので愚直にあらかじめ1の個数を数ればよい（ここでようやく解説と同じところまできた）
  • ん～XOR気づきたかったね(´；ω；`)ｳｯ…

ソースコード

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

#include<iostream>
#include<vector>
#include<algorithm>
#include<cctype>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#include<tuple>

#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 SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)

using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;


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 100005
int dx[4] = { 1,0,0,-1 };
int dy[4] = { 0,1,-1,0 };
const ll MOD = 1e9 + 7;
const ll INF = 1e14 + 7;


int main() {

	string s1, s2;

	int s1_siz = s1.size();
	int s2_siz = s2.size();

	vector<int> a(s1.size() + 10, 0);

	for (int i = 1; i <= s1.size(); i++)
	{
		a[i] = s1[i - 1] - '0';
	}

	//累積XOR
	for (int i = 0; i < s1.size(); i++)
	{
		a[i + 1] ^= a[i];
	}

	int cnt = 0;
	for (int i = 0; i < s2.size(); i++)
	{
		if (s2[i] == '1') {
			cnt++;
		}
	}

	cnt %= 2;
	int ans = 0;
	for (int i = s2_siz; i <= s1_siz; i++)
	{
		int tmp = a[i] ^ a[i - s2_siz];
		if (tmp % 2 == cnt) {
			ans++;
		}
	}

	cout << ans << endl;


	return 0;

}

つなげておいても損がなさそうならつなげておく・・・・

競プロ 2019 AtCoder diverta 400 文字列 損がなさそうならつなげておく

diverta 2019 Programming Contest C AB Substrings

問題概要

N個の文字列が与えられる．これらの文字列を好きな順番でつなげて連結し，1つの文字列を作るとき，文字列に含まれる部分文字列"AB"の個数が最大になるようにする．

問題リンク

https://atcoder.jp/contests/diverta2019/tasks/diverta2019_c

制約

1\leq N \leq 10^{4}
2\leq |S_{i}| \leq 10
S_{i}は英大文字からなる文字列である

考察

  • B****Aと****AとB****のものを組み合わせることまでは見えたけどどうつなげるのが最適なのかが見えてこなかった・・・・・・
  • これをよく見ると，B****Aを全てつなげておくと1つのB****Aとして見てもよさそうということがわかる（左右のBとAを有効に使いたいので）
  • B****Aをつなげて1つの塊として見られたとすると，次は****AとB****をつなげるのだが，ここで2つ場合分けができる．

　1.B****Aが0個の場合
　2.B****Aが1個以上ある場合

1の場合は****AとB****をつなげるしかないのでmin(***Aの個数，B****の個数)となる．2の場合はB****と****Aのうち1つずつはをB****Aの左右につなげることができるのでこれをまずつなげる．なぜか？？これは，B****Aの左右につなげることで，部分文字列"AB"が2つ生成できるためである．その後，余ったものを使ってmin(***Aの個数，B****の個数)により"AB"をつなげる．そして，文字列内のもとから存在している"AB"の個数を加えれば最大となる．

まとめると，
　1.B****Aが0個の場合はmin(***Aの個数，B****の個数)+ もとから文字列内に存在している"AB"の個数

　2.B****Aが1個以上ある場合は，***Aの個数，B****の個数がそれぞれ1個以上存在しているならば，それをつなげる．その後min(***Aの個数，B****の個数)+ もとから文字列内に存在している"AB"の個数を加える


ん～B****Aをつなげられるだけつなげても悪くなることはなさそうということに気づきたかった・・・・難しい・・・・・

精進して次は解けるようにします！！

ソースコード

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

#include<iostream>
#include<vector>
#include<algorithm>
#include<cctype>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<set>

#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 SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)

using namespace std;
typedef pair<int, int> pii;

typedef long long int ll;

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 5005
const ll INF = 1e9 + 7;


int dx[4] = { 1,0,0,-1 };
int dy[4] = { 0,1,-1,0 };

const ll MOD = 1e9 + 7;

int main() {

	int n;
	cin >> n;
	vector<string> a(n);

	int a_end = 0;
	int b_begin = 0;
	int ba = 0;

	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
		if (a[i][0] == 'B' && a[i].back() == 'A')
		{
			ba++;
		}
		else if (a[i].back() == 'A')
		{
			a_end++;
		}
		else if (a[i][0] == 'B')
		{
			b_begin++;
		}
	}

	int cnt = 0;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < a[i].size() - 1; j++)
		{
			if (a[i].substr(j, 2) == "AB")
			{
				cnt++;
			}
		}
	}
	
	int ans = max(ba - 1,0);//baを1つにまとめる
	
	if (ba > 0)
	{
		if (a_end > 0)
		{
			a_end--;
			ans++;
		}
		if (b_begin > 0)
		{
			b_begin--;
			ans++;
		}
	}
	
	ans += min(a_end, b_begin);

	cout << ans + cnt << endl;

	return 0;
}

プランクトンサミット参加記

プランクトンサミット

プランクトンサミットに参加してきました！！！


今回のプランクトンサミットではサイボウズ東京様にお邪魔させていただきました。ありがとうございました。眺めが良かったです！！！


さて、プランクトンサミットには競プロerとして参加しました。プランクトンサミットでは以下のタスクをしようと思って持っていきました。

  • ゼミ資料スライド作成（してません）
  • 論文読む（してません）
  • 競プロをする（しました）

結局競プロしかしていませんが（汗）

まあそれはいいとしてTLよく見る強い方にたくさんお会いできました。けんちょんさんにモフモフされたり

あっとさんアイコンを書いたり

ｼﾝﾔｶﾄｰ氏が来たり

直大さんにお会いして直筆サイン入りAtCoderステッカーをいただいたり（ありがとうございます！）

バチャをやったり・・・・・

ん～楽しすぎた・・・・・

私はオンサイトにいけるほど強くないのでこういう機会でしか競プロerの方々にお会いできないので強くなってオンサイトでお会いできるように今後も競プロの精進を頑張っていきたいと思いました。

各位本当にお世話になりました！！ありがとうございました！！！！

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

2019 競プロ AtCoder CSPCO2019 400 上書きは逆順から見るといい

CPSCO2019 Session3 D Decode RGB Sequence

問題概要

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

問題リンク

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

制約

3\leq N \leq 10^{5}
|S| = N
Sは'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;
}