AtCoder Regular Contest 098 D - Xor Sum 2

題名の破壊力半端ないよね。

問題文

D - Xor Sum 2

ほげ

最初に式について吟味してあげましょうって感じ問題。
n = 2*10^5なので、O(n^2)無理なんだよね。なので、式とにらめっこ。

そうすると条件を満たしているとき、各ビットについて、そのビットがたっている数字はひとつまでしか許されないという制約が見えてきます。

尺取りできそうですね。
「l を固定したときに、(l, r) が条件を満たすような最大の r を f(l) とおきます。すると、f は l に対して広義単調増加です。」
educationalでは尺取りできる根拠としてこう書いてありますね、なるほどという感じです。
この考え方すっごい大事で、コーディングするときもこの感覚でやるとなかなかきれいにできるみたい。

これがそれを意識したコード

 
int main(){
	int n;cin >> n;
	vector<int> v(n);
	REP(i,n)cin >> v[i];
	
	int r = 0;
	int now_sum = 0;
	int now_xor = 0;
	ll ans = 0;
	for(int l = 0;l < n;l++){
		while(r < n && (now_sum+v[r]) == (now_xor^v[r])){
			now_sum += v[r];
			now_xor ^= v[r];
			r++;
		}
		ans += r - l;
		now_sum -= v[l];
		now_xor ^= v[l];
	}
	
	cout << ans << endl;
	
	return 0;
}

これが意識していないコード(尺取り虫の気持ちになったコード)

int main(){
	
	int n;cin >> n;
	vector<ll> v(n);
	REP(i,n)cin >> v[i];
	
	ll ans = 0;
	
	int r = 0,l = 0;
	ll now_xor = v[0];
	ll now_sum = v[0];
	
	while(r < n-1){
		while(now_sum == now_xor && r < n-1){
			r++;
			now_sum += v[r];
			now_xor ^= v[r];
		}
		while(now_sum != now_xor && l <= r){
			ans += r - l;
			now_sum -= v[l];
			now_xor ^= v[l];
			l++;
		}
	}
	
	while(l <= r){
		ans += r - l + 1;
		l++;
	}
	
	cout << ans << endl;
	
	return 0;
}

だいぶ違いますね～。いい勉強になりました。