第一回日本最強プログラマー学生選手権-予選- C - Cell Inversion(500)

C - Cell Inversion

概要

正整数Nに対し、BとWからなる長さ2 * Nの文字列が与えられる。
この文字列の異なる2文字を選び、その間の文字を反転する(B->W, W->B)操作を繰り返す。
「全ての文字を1度ずつ選んで文字列に操作を行い、操作後の文字列が全てWとなる」ような操作の通り数を求めよ。(mod 10^9+7 して出力)

制約

1 ≦ N ≦ 10^5

方針

l文字目からr文字目までを反転する操作は次の3つに分解できる。

• 1文字目からl-1文字目までを反転
• 1文字目からr-1文字目までを反転
• r文字目を反転

よって、すべての文字を両端に選ぶ操作は次の2操作と等価である。
①1から2*Nまでのiについて、1文字目からi-1文字目までを反転
②各操作で右端に選ばれた文字を反転

①の操作をすべてのiで行うと、奇数番目の文字が反転されることになる。
②の操作の通り数は、①の操作後の文字列を用いて次のように求めることが出来る。
(変数: cnt, ans)

• 文字列を先頭から見ていく
• 文字がWならcntを+1する
• 文字がBならans にcntをかけた後、cntを-1する

ただし、①の操作後にWとBの文字数が等しくない場合は、全ての文字をWにすることができないため、0を出力する。

感想

解説放送通りです。
www.youtube.com

解答

Submission #7143943 - Japanese Student Championship 2019 Qualification

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
ll MOD = 1e9 + 7;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	ll N;
	cin >> N;
 
	string S;
	cin >> S;
 
	vector<int> T(2 * N);
	for(int i = 0; i < 2 * N; i++){
		T[i] = (S[i] == 'B' ? 1 : 0);
		if(i % 2 == 0) T[i] = 1 - T[i];
	}
 
	ll cnt = 0LL;
	rep(i, 2 * N) cnt += T[i];
	if(cnt != N){
		cout << 0 << endl;
		return 0;
	}
 
	ll ans = 1LL;
	ll t = 0LL;
	rep(i, 2 * N){
		if(T[i] == 0){
			t++;
		}else{
			ans *= t;
			ans %= MOD;
			t--;
		}
	}
 
	for(ll i = 1LL; i <= N; i++){
		ans *= i;
		ans %= MOD;
	}
 
	cout << ans << endl;
 
}