エクサウィザーズ 2019 : C - Snuke the Wizard

久々に良いスコアが出た。しょうもないミスしなければ国内3位だったのにね。
https://atcoder.jp/contests/exawizards2019/tasks/exawizards2019_c

問題

横１列にN個のマスがあり、それぞれマス目に記号がふってある。
初期状態で各マス１個ずつコマがあるとする。

ここでQ個のクエリが与えられる。
各クエリでは、指定された記号のマス目にのるコマがあると、それらを全部同時に左右いずれか指定された方に１マス動かす。
その際、両端のマスからはみ出たコマは取り除くとする。

全クエリを処理したとき、マス目に残ったコマはいくつか。

解法

初期位置があるマスにあるコマが途中左からはみ出たとする。
その場合、もともとそのコマより左にあるコマは、やはりはみ出るはずである。

よって、左からはみ出る最も右側のコマと、右からはみ出る最も左側のコマをそれぞれ二分探索しよう。

int N,Q;
string S;
string A[202020],B[202020];

int outL(int cur) {
	if(cur>=N) return 0;
	int i;
	FOR(i,Q) {
		if(S[cur]==A[i][0]) {
			if(B[i]=="L") cur--;
			if(B[i]=="R") cur++;
		}
		if(cur<0) return 1;
		if(cur>=N) return 0;
	}
	return 0;
}

int outR(int cur) {
	if(cur<0) return 0;
	int i;
	FOR(i,Q) {
		if(S[cur]==A[i][0]) {
			if(B[i]=="L") cur--;
			if(B[i]=="R") cur++;
		}
		if(cur<0) return 0;
		if(cur>=N) return 1;
	}
	return 0;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q>>S;
	FOR(i,Q) cin>>A[i]>>B[i];
	
	int L=-1;
	for(i=20;i>=0;i--) if(outL(L+(1<<i))) L+=1<<i;
	int R=N;
	for(i=20;i>=0;i--) if(outR(R-(1<<i))) R-=1<<i;
	
	int ret=N;
	FOR(i,N) if(i<=L || i>=R) ret--;
	
	cout<<ret<<endl;
	
	
}

まとめ

いつもより100/200ptが簡単だったね。