kmjp's blog

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

TopCoderOpen 2022 Wildcard : Medium DominatedSubstrings

SRM

Mediumは落としたけどHardをすんなり通せたのでレートは割と上昇。
https://community.topcoder.com/stat?c=problem_statement&pm=17774

問題

ABCで構成される文字列Wがある文字xでprefix-dominatedであるとは、Wのprefix中のA,B,Cの登場頻度をカウントすると、文字xが半数以上を占めていることを意味する。
また、文字列Wがdominatedであるとは、Wがある文字xでprefix-dominatedであり、かつWを反転したものもある文字yでprefix-dominatedであることを意味する。

文字列Sが与えられる。Sの部分文字列のうち、dominatedであるものの最大長と、その頻度を答えよ。

解法

部分文字列の左端Lを総当たりし、prefix-dominatedである最大の右端を求めよう。
これをf(L)とする。
左端を定めたら、Sの左端以降の文字列に対し、prefix-dominatedとなるprefixの最大長を求めよう。
以下のコードでは、(prefixにおけるxの登場頻度)-(prefixにおけるx以外の登場頻度)の区間最小値を求めるSegTreeを二分探索している。
ただ、これはかなり時間が厳しいので、(prefixにおけるxの登場頻度)-(prefixにおけるx以外の登場頻度)=-1となる左端に最寄の右端を取るだけでも行けるはず。

同様に、Sの右端Rに対し、Sの右端より前の文字列を逆向きに見て行った場合に、やはりprefix-dominatedとなる最小の左端を求めよう。これをg(R)とする。

最後に右端Rに対し、dominatedとなる最小の左端Lを求める。
これはL≦g(R)かつf(L)≧Rとなる最大のLを求めればよいが、これはf(L)を区間最大値を求めるSegTreeに乗せ、二分探索をすればよい。

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_2 {
public:
	vector<V> val;
	static V const def=-(1<<20);
	V comp(V l,V r){ return max(l,r);};
	
	SegTree_2(){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 P[3][303030];
int Q[3][303030];
SegTree_1<int,1<<19> st[3],st2[3];
SegTree_2<int,1<<19> ra;

int R[303030];

class DominatedSubstrings {
	public:
	vector <int> find(int N, string prefix, int seed, int pA, int pB, int pC) {
		ll state=seed;
		vector<int> S;
		FORR(c,prefix) S.push_back(c-'A');
		while(S.size()<N) {
    		state = (state * 1103515245 + 12345) %(1LL<<31);
		    ll v = (state/32)%(pA + pB + pC);
		    if(v<pA) S.push_back(0);
		    else if(v<pA+pB) S.push_back(1);
		    else S.push_back(2);
		}
		
		int i,j,x,y;
		FOR(j,3) {
			FOR(i,N) {
				P[j][i+1]=P[j][i];
				if(S[i]==j) P[j][i+1]++;
				else P[j][i+1]--;
				st[j].update(i+1,P[j][i+1]);
			}
		}
		FOR(j,3) {
			for(i=N-1;i>=0;i--) {
				Q[j][i]=Q[j][i+1];
				if(S[i]==j) Q[j][i]++;
				else Q[j][i]--;
				st2[j].update(i,Q[j][i]);
			}
			
		}
		
		FOR(i,N) {
			j=i;
			y=S[i];
			for(x=18;x>=0;x--) if(j+(1<<x)<=N) {
				if(st[y].getval(i+1,j+(1<<x)+1)>=P[y][i]) j+=1<<x;
			}
			ra.update(i,j);
		}
		int mal=0,cnt=0;
		for(i=N-1;i>=0;i--) {
			j=i;
			y=S[i];
			for(x=18;x>=0;x--) if(j-(1<<x)>=0) {
				if(st2[y].getval(j-(1<<x),i)>=Q[y][i+1]) {
					j-=1<<x;
				}
			}
			y=j;
			if(i-y<mal) continue;
			for(x=18;x>=0;x--) if(y+(1<<x)<=i) {
				if(ra.getval(y,y+(1<<x))<=i) {
					y+=1<<x;
					if(i-y<mal) break;
				}
			}
			if(i-y>mal) mal=i-y, cnt=0;
			if(i-y==mal) cnt++;
		}
		
		return {mal+1,cnt};
	}
}

まとめ

本番あと少しで通せてたな…もったいない。