X or Sum2 ~ABC 098 D~

Atcoder Python

※途中投稿です

問題文

長さ N の整数列A があります。

次の条件を満たす整数  l,  r (  1 ≤ l ≤ r ≤ N ) の組の個数を求めてください。

  • A[l] xor A[l+1] xor ... xor A[r] = A[l] + A[l+1] + ... + A[r]  

 

ソースコード(Python3)

N=int(input())
A=list(map(int,input().split()))
cur=A[0]
ans=0
rp=1

for lp in range(N):
　while rp<N and cur & A[rp]==0:
　　cur+=A[rp]
　　rp+=1
　ans+=rp-lp
　cur-=A[lp]

print(ans)

考え方

lp:lを見るポインタに相当

rp:rを見るポインタに相当

 

  • curに値（和）を蓄積していって、rに相当する所の論理積を取り0ならばrをずらす

二つの数の論理積が0

→和を取った時に繰り上げがない

→和とxorは等しくなる(和とxorの違いは双方に1があった時のみ)

 

 

  • 終わったらcurからlpの値を取り除く

この時、curにいくつかの値が蓄積していれば、

(ex.A[0]=100,A[1]=010,A[2]=001)

lpの値を抜き取っても、

残りの部分列は和とxorが等しい列になっている

(ex.A[1]+A[2]=011=A[1]xorA[2])

rpはそのまま次の判定に用いれる

 

振り返って

par.hateblo.jp