XXOR [AtCoder Beginner Contest 117 D]

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

前提知識

• 桁DP

解説

https://atcoder.jp/contests/abc117/submissions/4166833

桁DPをする。
2進数で60桁を想定して解く（10^12なので、もうちょっと小さいが、横着した）。
dp[dgt][isless] := 上位dgtビットが確定していて、確定部分がKと比べて既に小さいか（isless）のときの総和の最大値
XOR問題は各ビットで独立して操作を行う方針がよく取られる。
今回の問題では完全に独立している訳ではなく、K以下であるという制約から、ある桁で1が置けない状況がある。
なので、桁DPを使って解いていく。
　
桁毎に0を置くか、1を置くかを考えていく。
0は無条件におけるが、1はKを超えてしまう場合は置くことができない。
あとは、適切に初期化をして進めれば答え。

int N;
ll K, A[101010];
ll dp[61][2]; // dp[dgt][isless]
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    rep(i, 0, N) cin >> A[i];
 
    rep(dgt, 0, 61) rep(isless, 0, 2) dp[dgt][isless] = -infl;
    dp[0][0] = 0;
 
    rep(dgt, 0, 60) rep(isless, 0, 2) if(0 <= dp[dgt][isless]) {
        int d = 59 - dgt;
        ll msk = 1LL << d;
 
        int zero = 0, one = 0;
        rep(i, 0, N) {
            if (A[i] & msk) one++;
            else zero++;
        }
 
        // 0
        int isless2 = isless;
        if (K & msk) isless2 = 1;
        chmax(dp[dgt + 1][isless2], dp[dgt][isless] + one * msk);
 
        // 1
        if ((K & msk) or isless == 1) {
            chmax(dp[dgt + 1][isless], dp[dgt][isless] + zero * msk);
        }
    }
 
    cout << max(dp[60][0], dp[60][1]) << endl;
}