tooh’s diary

半角全角、常体敬体が入り乱れるカオス

4/10 AtCoder

こんばんは。毎日めちゃくちゃ疲れているとーです。

ARC098D

数列の和とXORが等しくなる部分はいくつありますか、という問題
基本的に、XORと普通の和では、同じビットが立っているところはXORでは0になるので、XORの方が小さくなるということを念頭に置く
(想定解は、数列の各項を二進数に直し、ビットが立っている位を見ていって、その個数が1個以下であるならば足す、それ以外であれば左端を除く、ということを繰り返すものだったが今回は愚直に足していく方を採用)

解き方はいたって簡単で、端っこを固定し(ここでは左端)、伸ばせるところまで右を伸ばした後、右から左の数を引いて足す(これにより、固定した左端からスタートする数列の数が数えられたことになる)これを、左端が数列の右端に来るまで続ければよい