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

Dまでは良かったんだけどね…。
https://atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_c

問題

白黒で構成された2N個のマスの列がある。
このうちある区間を選び、区間内を白黒反転させる、ということをN回行う。
その際、各マスは区間の左端または右端のいずれかを1回ずつ担当するものとする。

最終的に全マス白となるような反転順は何通りか。

解法

まず、各マスが左端となるか右端となるかは一意に定まる。
また、それさえ決まればどの左端と右端とペアにするかは結果に依存しない。

そこで、まず左端右端を決めてみよう。
列の左端から順に、各マス左端と右端どちらになるか見ていく。
もし今見ている点が右端になる場合、左隣のマスと反転回数が等しくなる、すなわち左隣と同じ色でなければならない。
逆に右端となる場合は、左隣のマスより反転回数が1回増えるので、左隣と逆の色でなければならない。

こうして左端右端が確定したら、両者の数が等しいことを確認したうえで、端から順にペアを組んでいこう。
右端担当のマスに来たら、ペアが未確定の左端のどれかとペアにする、と考えて掛け算を繰り返せばよい。

int N;
string S;
ll mo=1000000007;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S;
	int cur=0;
	ll ret=1;
	FORR(c,S) {
		if(c=='B') {
			if(cur%2==1) {
				ret=ret*cur%mo;
				cur--;
			}
			else {
				cur++;
			}
		}
		else {
			if(cur%2==1) {
				cur++;
			}
			else {
				ret=ret*cur%mo;
				cur--;
			}
		}
	}
	if(cur>0) ret=0;
	FOR(i,N) ret=ret*(i+1)%mo;
	cout<<ret<<endl;
	
}

まとめ

ちょっと悩んだけど割とすぐ思いつけた。