<-- home

AtCoder ABC117 D

April 24, 2020

https://atcoder.jp/contests/abc117/tasks/abc117_d

XORの性質について考察して、桁DPに落とす。

  • XOR => 2進数で考えて桁ごとに計算できる
  • なので40ビットで表せる

  • Xのi-th bitと、それぞれのi-th bitとのXORの総和は

    • Xのi-th bitが1なら、それぞれのi-th bitが0となっているものの個数
    • Xのi-th bitが0なら、1となっているものの個数

実装

#define MAX_BIT 40
i64 dp[MAX_BIT + 1][2];

#define INF 1152921504606846976

int main() {
    i64 N, K; cin >> N >> K;
    vector<i64> A(N);
    REP(i, N) cin >> A[i];

    REP(i, MAX_BIT + 1) REP(j, 2) dp[i][j] = -INF;
    dp[0][0] = 0;

    i64 p = 1LL << 40;
    REP(l, MAX_BIT) {
        p /= 2;

        i64 Ki = K / p;
        K %= p;

        i64 n1 = 0;
        REP(j, N) {
            n1 += A[j] / p;
            A[j] %= p;
        }

        REP(smaller, 2) {
            for (i64 i = 0; i <= (smaller ? 1 : Ki); i++) {
                chmax(dp[l + 1][smaller || i < Ki], dp[l][smaller] + (i == 1 ? (N - n1) : n1) * p);
            }
        }
    }

    cout << max(dp[MAX_BIT][0], dp[MAX_BIT][1]) << endl;

    return 0;
}