kmjp's blog

競技プログラミング参加記です

Codeforces #450 Div2 E. Maximum Questions

なんか無駄に問題設定がややこしいな。
http://codeforces.com/contest/900/problem/E

問題

N文字の文字列Sがある。
Sの各文字はa,b,?のいずれかである。

ここでM文字の文字列Tを考える。
Tはabab...とabが交互に続く。

S中の互いに重ならない領域でTと一致する部分文字列をできるだけ多く抜き出したい。
その際S中の?はあa,bどちらにでも変更することが できる。
Tと同じ部分文字列を多く抜き出す抜き出し方のうち、?を変更する数の最小値を求めよ。

解法

まず前処理として、Sの各位置に対しその位置を先頭として後続の?をどうにかするとTと一致させられるか、またその時何個の?を含むかを求めよう。
これは先頭位置の偶奇に対しRMQを用いて各文字が条件を満たせるかどうかを管理して行ったが、BITなどで条件を満たせない位置の数の総和を求めたりでも解くことができる。

次に抜き出しの数と?の置き換え数をDPで前から順次処理していく。
x文字目を先頭とする部分文字列がTを抜き出す場合、直前にTを抜き出した位置は(x-M+1)文字目以前の位置でなければならない。
Tを抜き出す数を最大化させる条件より、そのような位置のうち、抜き出し数が最大となるものから選ばなければならない。
幸い各位置においてそこまでの抜き出し数は単調増加になるので、RMQ+二分探索などでその範囲を特定することができる。
あとはそのような直前の位置に対し、?の置き換え数が最小のものをやはりRMQで選ぼう。

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=1<<20;
	V comp(V l,V r){ return min(l,r);};
	
	SegTree_1(){val=vector<V>(NV*2,def);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=v;
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};
template<class V,int NV> class SegTree_1_max {
public:
	vector<V> val;
	static V const def=0;
	V comp(V l,V r){ return max(l,r);};
	
	SegTree_1_max(){val=vector<V>(NV*2,def);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=v;
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};

int N,M;
string S;
SegTree_1<int,1<<20> bt[2],rep;
SegTree_1_max<int,1<<20> step;

int sum[1101010];
int num[1101010];
int st[1101010];
int trep[1101010];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S>>M;
	FOR(i,N) {
		
		sum[i+1]=sum[i]+(S[i]=='?');
		bt[0].update(i,N);
		bt[1].update(i,N);
		
		if(S[i]=='a') {
			bt[(i%2)^1].update(i,i);
		}
		if(S[i]=='b') {
			bt[(i%2)].update(i,i);
		}
	}
	int mstep=0,mrep=0;
	FOR(i,N) {
		if(bt[i%2].getval(i,i+M)>=i+M) {
			num[i]=sum[i+M]-sum[i];
			
			x=step.getval(0,i-M+1);
			st[i]=x+1;
			if(x==0) {
				trep[i]=num[i];
			}
			else {
				y=-1;
				for(j=20;j>=0;j--) {
					if(y+(1<<j)>=i) continue;
					if(step.getval(0,y+(1<<j))<x) y+=1<<j;
				}
				trep[i]=num[i]+rep.getval(y,i-M+1);
			}
			
			if(st[i]>mstep) mstep=st[i],mrep=101010;
			if(st[i]==mstep) mrep=min(mrep,trep[i]);
			
		}
		else {
			num[i]=101010;
			st[i]=0;
			trep[i]=101010;
		}
		
		
		step.update(i,st[i]);
		rep.update(i,trep[i]);
	}
	cout<<mrep<<endl;
}

まとめ

これ系いつも解けないので久々にまともに解けてよかった。