エクサウィザーズ 2019 C - Snuke the Wizard(500)

C - Snuke the Wizard

概要

N個のマスが直線状に並んでいて、そのマスにはアルファベットが記載されている。また各マスの上には一体ずつゴーレムが配置されている。

Q個の命令があり、命令iはマスのアルファベットに対応するアルファベットtiと、"L"（左）か"R"（右）のどちらかであるdiからなる。
各命令ではtiのアルファベットが記載されているマスのゴーレムがすべてdiに対応して左か右かのどちらかのマスに1マス動く。
（各マスには何体でもゴーレムが乗ることができる。また一度の命令で複数のマスの複数のゴーレムが動くこともある。）

一番左のマスのゴーレムはさらに左に動くと消滅し、一番右のマスのゴーレムはさらに右に動くと消滅する。
Q個の命令を終えたとき、消滅しないで残っているゴーレムは何体あるか。

制約

1 ≦ N, Q ≦ 2 * 10^5

方針

各命令によるゴーレムの動きをすべて直接実装すると、O(NQ)かかるため間に合わない。

「あるゴーレムが他のゴーレムを飛び越えることがない」ということが重要。
するとあるマスのゴーレムが左から消滅する場合、そのマスより左のゴーレムはすべて左から消滅することになる。
なので、２分探索で左から消滅するゴーレムのうち最も右にあるものを探索することができる。
右から消滅するゴーレムも同様である。

感想

左から消滅するゴーレムの２分探索はupper_boundを使い、右から消滅するゴーレムの２分探索はlower_boundを使いました。

解答

Submission #4779987 - ExaWizards 2019

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
int max_N = 1e7;
 
int N, Q;
string s;
vector<char> t;
vector<char> d;
 
bool lcond(int x){
	int ok = N;
	int ng = -1;
	int pos = x;
	if(pos <= ng) return false;
	if(pos >= ok) return true;
 
	for(int i = 0; i < Q; i++){
		if(t[i] == s[pos]){
			if(d[i] == 'L'){
				pos--;
			}else{
				pos++;
			}
			// cout << x << "," << i << "," << pos << endl;
		}
 
		if(pos == ng) return false;
		if(pos == ok) return true;
	}
	return false;
}
 
bool ucond(int x){
	int ok = -1;
	int ng = N;
	int pos = x;
	if(pos >= ng) return false;
	if(pos <= ok) return true;
 
	for(int i = 0; i < Q; i++){
		if(t[i] == s[pos]){
			if(d[i] == 'L'){
				pos--;
			}else{
				pos++;
			}
			// cout << x << "," << i << "," << pos << endl;
		}
 
		if(pos == ng) return false;
		if(pos == ok) return true;
	}
	return false;
}
 
// condを満たす最小のxを求める(lower_bound)
// 全てのxが条件を満たさない場合はnを返す(nはとりえない値)
int lower_bound_cond(){
	int lb = -1, ub = max_N;
 
	while(ub - lb > 1){
		int mid = (lb + ub) / 2;
		bool ok = lcond(mid);
		// cout << mid << "," << ok << endl;
		if(ok) ub = mid;   // Answer is in (lb, mid]
		else lb = mid;            // Answer is in (mid, ub]
	}
 
	// now lb + 1 = ub
	return ub;
}
 
// condを満たす最大のxを求める(upper_bound)
// 全てのxが条件を満たさない場合は-1を返す(-1はとりえない値)
int upper_bound_cond(){
	int lb = -1, ub = max_N;
 
	while(ub - lb > 1){
		int mid = (lb + ub) / 2;
		bool ok = ucond(mid);
		// cout << mid << "," << ok << endl;
		if(ok) lb = mid;   // Answer is in [mid, ub)
		else ub = mid;            // Answer is in [lb, mid)
	}
 
	// now lb + 1 = ub
	return lb;
}
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	cin >> N >> Q;
	cin >> s;
 
	rep(i, Q){
		string a, b;
		cin >> a >> b;
 
		t.push_back(a[0]);
		d.push_back(b[0]);
	}
 
	// cout << "calc lfall:" << endl;
	int lfall = upper_bound_cond();
	// cout << "lfall = " << lfall << endl;
	// cout << "calc ufall:" << endl;
	int rfall = lower_bound_cond();
	// cout << "rfall = " << rfall << endl;
 
	int fall = (lfall == max_N ? 0 : lfall + 1) + (rfall == -1 ? 0 : N - rfall);
	cout << N - fall << endl;
}