Codeforces #953 : Div2 E. Computing Machine

不参加だった回。
https://codeforces.com/contest/1978/problem/E

問題

2つのバイナリ文字列A,Bがあったとき、以下の処理を行える。

• A[i]=A[i+2]=0の時、B[i+1]=1にできる
• B[i]=B[i+2]=1の時、A[i+1]=1にできる

バイナリ文字列S,Tが与えられる。クエリとしてその部分列が指定されるので、それらをA,Bとしたとき、上記処理によりA中の1をどれだけ増やせるか判定せよ。

解法

あらかじめA=S,B=Tとしたとき、Aの各位置が1になるかどうかを判定しておく。

各クエリにおいて、Aのうち先頭2文字と末尾2文字以外は、部分列の位置に寄らずこの初期状態の判定結果と等しくなる。
あとは先頭2文字と末尾2文字がどうなるか愚直に判定すればよい。

int T,N;
string A,B;
int S[202020];
int Q,L,R;

int check(int i,int L,int R) {
	if(A[i]=='1') return 1;
	int lef=0,ri=0;
	if(i-1>=L&&B[i-1]=='1') lef=1;
	if(i-2>=L&&A[i-2]=='0') lef=1;
	if(i+1<=R&&B[i+1]=='1') ri=1;
	if(i+2<=R&&A[i+2]=='0') ri=1;
	return lef&ri;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>A>>B;
		FOR(i,N) S[i+1]=S[i]+check(i,0,N-1);
		cin>>Q;
		while(Q--) {
			cin>>L>>R;
			L--;
			R--;
			int ret=0;
			if(R-L>=5) {
				ret+=S[R-2+1]-S[L+1+1];
				ret+=check(L,L,R);
				ret+=check(L+1,L,R);
				ret+=check(R-1,L,R);
				ret+=check(R,L,R);
			}
			else {
				for(i=L;i<=R;i++) ret+=check(i,L,R);
			}
			cout<<ret<<endl;
		}
	}
}

まとめ

何がさせたかったのかよくわからない問題。