Codeforces #316 Div2 C. Replacement

色々グダグダだった回。Div2で良かったか…。
http://codeforces.com/contest/570/problem/C

問題

アルファベットとピリオドで構成された文字列Sがある。
f(S)とは、連続した２つのピリオドを１つに置換する、という処理を最大何回行えるかを示す。

ここでN文字の文字列SとM個のクエリが与えられる。
各クエリは位置X[i]と文字C[i]からなり、SのX[i]文字目をC[i]に置き換えることを意味する。

順次クエリを処理していくとき、その都度f(S)を答えよ。

解法

f(S)を言い換えると、(S中のピリオドの数)-(S中の連続したピリオド集合の数)と言える。
よってクエリを処理しながら、上記２つの値を更新していけばO(N+M)で処理を終えられる。

(S中の連続したピリオド集合の数)は、1文字目またはアルファベットの直後に来るピリオドの数を数えればよい。
Mが大きいので、coutを使うのは危険。

int N,M;
string S;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	cin>>S;
	
	N++;
	S="a"+S+"a";
	int np=0,ps=0;
	
	FOR(i,N) if(S[i]=='.') {
		np++;
		if(S[i-1]!='.') ps++;
	}
	
	FOR(i,M) {
		cin>>x>>s;
		if(s==".") {
			if(S[x]!='.') {
				np++;
				if(S[x-1]!='.') ps++;
				if(S[x+1]=='.') ps--;
			}
		}
		else {
			if(S[x]=='.') {
				np--;
				if(S[x-1]!='.') ps--;
				if(S[x+1]=='.') ps++;
			}
		}
		S[x]=s[0];
		_P("%d\n",np-ps);
	}
}

まとめ

最初(S中の連続したピリオド集合の数)を管理するのにsetでガチャガチャやろうとしたが、最終的にシンプルなコードになった。