AtCoder ARC #203 : D - Insert XOR

今回場合分けがしんどい問題が多いな。
https://atcoder.jp/contests/arc203/tasks/arc203_d

問題

バイナリ列Aが与えられる。また、1要素0/1反転するクエリが与えられる。
そのつど、以下の問題に答えよ。

• バイナリ列Bを考える。任意の隣接要素B[i],B[i+1]を選び、その間にB[i] xor B[i+1]を挿入することを繰り返しBをAにしたい。
• 初期状態としてあり得るBの最短長を答えよ。

解法

まずBからどのような形が作れるか考える。

• 00 → 間に0をいくらでも増やせる。
• 01・10 → 間に1をいくらでも増やせる。
• 11 → 最初0を間に1個増やせる。その後、1をいくらでも増やせる。

0を増やす手段は初期状態で00と0を2つ並べるしかない。
一方3個以上連続した0は、0を2個からつくれる。

よってAをまず2個以上連続した0の塊で分割する。
その際、間に1が1個以上入るが、その場合00100のように初期状態で00と00の間に1を1個でも入れておけば、01や10から1を増殖させ、また11の間に0を追加できるので、間はどんな形であっても、初期状態は1が1個あればよい。

あとは最初の00の手前と、最後の00の後に置くものを以下のどの形状にするか考えよう。

• 01xxx
• 1xxx
• xxx10
• xxx1

コーナーケースとして、00が1個もない場合に注意。

int N,A[202020];
int C[2],Q,X;
set<int> S;

int is(int i) {
	
	if(i==0) return A[i]==0&&A[i+1]==0;
	if(i<=0||i>=N-1) return 0;
	return A[i-1]&&A[i]==0&&A[i+1]==0;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		C[A[i]]++;
	}
	FOR(i,N) if(is(i)) S.insert(i);
	
	cin>>Q;
	while(Q--) {
		cin>>X;
		X--;
		for(i=X-3;i<=X+3;i++) S.erase(i);
		C[A[X]]--;
		A[X]^=1;
		C[A[X]]++;
		for(i=X-3;i<=X+3;i++) if(is(i)) S.insert(i);
		
		if(C[1]==0) {
			cout<<2<<endl;
		}
		else if(C[1]==1) {
			x=1;
			if(A[0]==1||A[N-1]==1) x=3;
			else if(A[1]==1||A[N-2]==1) {
				if(N==3) x=3;
				else x=4;
			}
			else {
				x=5;
			}
			cout<<x<<endl;
		}
		else if(C[1]==N) {
			cout<<N<<endl;
		}
		else if(S.size()==0) {
			int num=1;
			if(A[0]&&A[N-1]) num=2;
			else {
				if(A[0]==0) num++;
				if(A[N-1]==0) num++;
			}
			cout<<num<<endl;
		}
		else {
			int num=2*S.size()+S.size()-1;
			if(A[0]==0&&A[1]==1) num+=2;
			if(A[0]) num++;
			if(A[N-1]==0&&A[N-2]==1) num+=2;
			if(A[N-1]) num++;
			cout<<num<<endl;
		}
		
		
	}
	
}

まとめ

細かいところ詰めるのに手間取った。