AtCoder ABC 098 D - Xor Sum 2 (ARC 098 D) (水色, 500 点)

こんなしゃくとり法もあるのんな。面白いん。

ABC 098 D Xor Sum 2

問題概要

長さ の正の整数列 が与えられる。整数列の連続する部分列のうち、「xor 和と加算和とが等しい」という条件を満たすものを数え上げよ。

制約

• 
• 

数値例

1)
　
　
　答え: 5

(2), (2, 5), (5), (4), (6) の 5 個です

解法

「xor 和と加算和とが等しい」という条件が、「条件を満たす区間の部分区間も条件を満たす」という構造になっていることは非自明かもしれません。そこが示せたら、あとはしゃくとり法を適用するだけになります。

基本的に「xor 和 <= 加算和」が成り立ちます。例えば x = 10101 (二進法)、y = 1001 (二進法) としたとき、

x xor y = 11100 (一の位が消えます) x + y = 11110 (一の位が繰り上がります)

という感じになり、x + y は繰り上がりが残るのに対し、x xor y は 1 が被ると消えてしまいます。そう考えると

x xor y = x + y ⇔ 二進法におけるどの桁を見ても $x$ と $y$ のうちビットが立っているのは高々一方のみ

となります。つまり条件は「どの桁を見てもビットが立っているのは高々 1 個のみ」と同値になります。ここまで来ると確かに「条件を満たす区間の部分区間も条件を満たす」という構造を満たしていることがわかります。

実装上は、「各桁ごとに」という考え方をせずに、直接 sum xor a[right] = sum + a[right] になるかどうかを判定した方が楽です。

#include <iostream>
#include <vector>
#include <set>
using namespace std;

int main() {
    /* 入力受け取り */
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    
    /* しゃくとり法 */
    long long res = 0;
    int right = 0;
    int sum = 0; // AND 和
    for (int left = 0; left < n; ++left) {
        while (right < n && (sum ^ a[right]) == (sum + a[right])) {
            sum += a[right];
            ++right;
        }
        res += right - left;
        if (left == right) ++right;
        else {
            sum -= a[left]; // a[left] を削除 (sum ^= a[left] でも OK)
        }
    }
    
    cout << res << endl;
}