yukicoder : No.2281 K → K-1 01 Flip

実装は軽めで考察が重めの問題。
https://yukicoder.me/problems/no/2281

問題

01で構成されるSが与えられる。
クエリとしてSの連続部分文字列と正整数Kが指定されるので、以下に答えよ。

• 文字列中に0または1がK個連続した箇所があるとき、1または0を(K-1)並べたものに置き換える、ということを任意回数に行えるとする。
• 最終的に最短何文字の文字列に置き換えられるか。

解法

文字列中の不変量は(0の個数)-(1の個数) % (2K-1)となる。
ただし、初期状態で0または1がK個以上並んだ箇所がないと処理は行えないし、処理を行った場合、最終的に0または1が(K-1)個並んだ箇所が残らないといけない。
一方、初期状態で0または1がK個以上並んだ箇所があれば、最終的に0または1が(K-1)個並び、もう片方も(K-1)個以下となる状態に持ち込める。

そこで、クエリ毎に「0または1がK個以上並んだ箇所」を高速に判定できればよい。
これは「左に何文字同じ文字が続くか」という情報を持つ配列を区間最大値を計算できるSegTreeに載せれば求められる。

int N,Q;
string S;
int L[202020],R[202020];
int P[2][202020];

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=0;
	// static V const def=1LL<<60; min
	V comp(V l,V r){ return max(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]=comp(v,val[entry]); //上書きかチェック
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};
SegTree_1<int,1<<20> LT;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q>>S;
	FOR(i,N) {
		if(i==0||S[i]!=S[i-1]) L[i]=1;
		else L[i]=L[i-1]+1;
		P[0][i+1]=P[0][i];
		P[1][i+1]=P[1][i];
		P[S[i]-'0'][i+1]++;
	}
	for(i=N-1;i>=0;i--) {
		if(i==N-1||S[i]!=S[i+1]) R[i]=1;
		else R[i]=R[i+1]+1;
		LT.update(i,L[i]);
	}
	
	while(Q--) {
		int A,B,K;
		cin>>A>>B>>K;
		A--,B--;
		int ok=0;
		if(A+K-1<=B) {
			if(R[A]>=K) {
				ok=1;
			}
			else {
				x=A+R[A];
				if(LT.getval(x,B+1)>=K) ok=1;
			}
		}
		int ret=B-A+1;
		if(ok) {
			int n0=P[0][B+1]-P[0][A];
			int n1=P[1][B+1]-P[1][A];
			int k=2*K-1;
			int c=((n0-n1)%k+k)%k;
			// 0をK-1個残す
			ret=min(ret,K-1+(K-1-c+k)%k);
			// 1をK-1個残す
			ret=min(ret,K-1+(c+K-1)%k);
			
		}
		cout<<ret<<endl;
	}
	
	
}

まとめ

01入れ替えるタイプの問題は、差を不変量に取るテク、覚えておかないとな。