Mister雑記

競プロ記事がメインになりますが、内容は気分次第です。

ARC098-D 「Xor Sum 2」 (500)

beta.atcoder.jp

概要

長さ Nの数列 A_iが与えられる。このとき、

 \displaystyle A_l + A_{l + 1} + \dots + A_r =
 \displaystyle A_l \hspace{1ex} xor \hspace{1ex} A_{l + 1} \hspace{1ex} xor \dots xor \hspace{1ex} A_r

を満たす (l, r)の組の数を求めよ。

制約

  •  1 \leq N \leq 2 \times 10^5
  •  0 \leq A_i \lt 2^{20}

解説

この問題で鍵となるのは、以下の和とxorの間に成立する等式である。

 \displaystyle A + B =
\displaystyle A \hspace{1ex} xor \hspace{1ex} B +
\displaystyle (A \hspace{1ex} and \hspace{1ex} B) \ll 1

右辺は分解すると、

  •  A \hspace{1ex} xor \hspace{1ex} Bは繰り上がりを無視した値
  •  (A \hspace{1ex} and \hspace{1ex} B) \ll 1は繰り上がりのみを考えた値

と解釈できる。和において繰り上がりが発生する条件は「同じ桁がどちらも1である場合」で、そのときその桁は0になって1つ上の桁に1を加えることになる、というのを式で表すと上の通りになる。

よって整数の組 (l, r)が条件を満たすことは、

任意の l \leq i \lt j \leq rについて、 A_i \hspace{1ex} and \hspace{1ex} A_j = 0

が成立することと同値となる。より直感的には、「 A_l, \hspace{1ex} A_{l + 1}, \hspace{1ex} \dots \hspace{1ex} A_rのbitが1つもかぶらない」とも言える。

これをそのまま尺取り法で実装してもいいのだが、尺取り法はバグりやすいため(個人差有)今回は二分探索で実装することにする。

まず lを固定したとき、上の条件は rについて単調性をもつことが分かる。言い換えると、「 l\leq r \leq r_0なら常に (l, r)は条件を満たし、逆に r \gt r_0なら常に (l, r)は条件を満たさない」という境界値 r_0が存在する。このとき条件を満たす組の数は r_0 - l + 1個となる。これを各 1 \leq l \leq Nについて全部求めて足し合わせればいい。

この r_0は二分探索により計算量 O(\log N)で求められるので、全体の計算量は O(N \log N)で十分間に合う。

ちなみに (l, r)が条件を満たすかの判定は、下のコードでは累積和と累積xorを使って問題文通りに判定している。これができるのは、和とxorについて

  •  A = (A + B) - B
  •  A = (A \hspace{1ex} xor \hspace{1ex} B) \hspace{1ex} xor \hspace{1ex} B

という性質が成り立つためである。

実装例

#include <iostream>

using namespace std;

using ll = long long;

int main() {
    int N;
    cin >> N;

    ll A[N + 1];
    for (int i = 1; i <= N; ++i) {
        cin >> A[i];
    }

    ll sum[N + 1], xorsum[N + 1];
    sum[0] = xorsum[0] = 0;
    // 累積和と累積xor どちらも1-indexed

    for (int i = 1; i <= N; ++i) {
        sum[i] = sum[i - 1] + A[i];
        xorsum[i] = (xorsum[i - 1] ^ A[i]);
    }

    ll ans = 0;
    for (int l = 1; l <= N; ++l) {
        int ok = l, ng = N + 1;
        // (l, ok)は条件を満たし、(l, ng)は条件を満たさない
        // このokとngの距離を縮めていくことで境界値r0を求める

        while (ng - ok > 1) {
            int mid = (ok + ng) / 2;
            if (sum[mid] - sum[l - 1] == (xorsum[mid] ^ xorsum[l - 1])) {
                ok = mid;
            } else {
                ng = mid;
            }
        }

        // 最終的なokが境界値r0となる
        ans += ok - l + 1;
    }

    cout << ans << endl;
    return 0;
}

答えの最大値は 10^{10}程度になるため、地味にintではオーバーフローすることに注意(1敗)。

感想

  • Xor Sumに比べれば非常に良心的。
  • xorと和の関係と尺取り法、二分探索を学べるいい典型問題だと思う。