Mister雑記

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

Codeforces Round #512 (Div2) - E 「Vasya and Good Sequences」 [2100]

codeforces.com

概要

正整数列 \{a_i\}に以下の操作を何度か施すことで、全てのXORを取った値が 0になるようにできるとき、 \{a_i\}を「良い数列」と呼ぶことにする。

  • 要素 a_iを任意に選ぶ。
  •  a_iを2進数表記し、任意の2つのbitを交換する。

長さ Nの正整数列 \{a_i\}の連続部分列で、「良い数列」であるものの個数を求めよ。

制約

  •  1 \leq N \leq 3 \times 10^5
  •  1 \leq a_i \leq 10^{18}

考察

まず操作について考える。正整数 aを2進数表記したときの 1の数を nとする。この aに上の操作を何度か施すことによって、 1の数が nであるような任意の数に変換できることが分かる。 したがって、 a_iの代わりに「 a_iを2進数表記したときの 1の数」だけを保持すればよい。この数列を \{b_i\}とする。


次に、ある数列が「良い数列」となる条件を調べる。XORの性質を考えると、以下のことが分かる。

  •  \{b_i\}に対して、「異なる2要素から 1ずつ引く」という操作を考える。この操作を繰り返すことで \{b_i\}を全て 0にできるとき、 \{b_i\}は「良い数列」である。

さらにこれは、証明が難しいが以下の2つの条件と同値になる。

  •  \{b_i\}の総和が偶数。
  •  \{b_i\}の最大値は、それ以外の値の総和以下である。

前者は明らか。後者については

  •  \{b_i\}を最大値とそれ以外に分ける。
  • 一方は最大値を 0になるまで減らし続ける。
  • もう一方は「それ以外の集合」の最大値を常に減らすようにする。

という戦略によって常に全て 0にできるはず。


よって上の2条件を満たす連続部分列の数を数え上げればいい。

まず1つ目の条件。 \{b_i\}の累積和を \{sum_i\}としたとき、 sum_r sum_lの偶奇が一致していることが条件となる。よって \{sum_i\}パリティからなる累積和を取れば、前者を満たす区間の数は十分高速に求まる。Zero-Sum Rangesと同じ手法。

ここから2つ目の条件を満たさないものを排除していくが、これは全ての区間を調べる必要はない。制約の 1 \leq a_i \leq 10^{18}から 1 \leq b_i \leq 60なので、長さ 61以上の区間は全て2つ目の条件を満たすことになる。よって長さ 60以下の区間だけ調べれば良い。

最大値を線形探索で求めると、計算量は 60 \times 60 \times n \leq 10^9程度になる。危ない数値だが、ループ内の処理は単純なので何とか間に合う。

実装例

累積和はindexがズレがちなので実装が疲れる。

#include <iostream>
#include <algorithm>

using namespace std;
using ll = long long;

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

    int b[N];
    for (int i = 0; i < N; ++i) {
        ll a;
        cin >> a;
        b[i] = __builtin_popcountll(a);
        // 立っているbitの数を数える 環境によっては使えないかも
    }

    ll sum[N + 1], psum[N + 1];
    // sum[i]  = 前からi個の累積和
    // psum[i] = j<=iかつsum[j]が奇数であるものの数 (parity sum)

    sum[0] = psum[0] = 0;
    for (int i = 0; i < N; ++i) {
        sum[i + 1] = sum[i] + b[i];
        psum[i + 1] = psum[i] + (sum[i + 1] % 2);
    }

    ll ans = 0;
    for (int r = 1; r <= N; ++r) {
        // sum[l]とsum[r]の偶奇が一致しているものを数え上げ
        if (sum[r] % 2 == 1) {
            ans += psum[r - 1];
        } else {
            ans += r - psum[r - 1];
        }
    }

    // 長さ60以下の区間を全探索
    for (int l = 0; l < N; ++l) {
        for (int r = l + 1; r <= min(N, l + 60); ++l) {
            int s = sum[r] - sum[l];  // b[l]+b[l+1]+...+b[r-1]
            if (s % 2 != 0) continue;

            int ma = *max_element(b + l, b + r);  // max(b[l], b[l+1], ..., b[r-1])
            if (ma * 2 > s) --ans;
        }
    }

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

感想

  • 方針は合っていたが証明ができず、確信が持てなかった。
  • 実装は実装でindexズレやら勘違いで無限にバグらせた。
  • なんか反省点が多い問題だった。