ABC 117

https://atcoder.jp/contests/abc117

A. Entrance Examination

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

B. Polygon

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

C. Streamline

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

D. XXOR

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

桁 DP で解ける問題だということをわかった上で自力 AC

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, K;
    cin >> N >> K;
    vll A(N);
    rep(i, N) cin >> A[i];

    vint Kbit;
    vvint Abit(N);
    int mx = 60;

    {
        ll t = K;
        rep(i, mx) {
            Kbit.push_back(t % 2);
            t /= 2;
        }
        reverse(all(Kbit));

        rep(i, N) {
            ll a = A[i];
            rep(j, mx) {
                Abit[i].push_back(a % 2);
                a /= 2;
            }
            reverse(all(Abit[i]));
        }
    }

    vector dp(mx + 1, vll(2));
    rep2(i, 1, mx + 1) {
        int t = Kbit[i - 1];
        ll cnt = 0;
        rep(j, N) {
            cnt += Abit[j][i - 1];
        }

        rep(d, 2) {
            if (d < t) {
                chmax(dp[i][1], dp[i - 1][0] * 2 + cnt);
            }
            if (d == t) {
                if (d == 0)
                    chmax(dp[i][0], dp[i - 1][0] * 2 + cnt);
                else
                    chmax(dp[i][0], dp[i - 1][0] * 2 + N - cnt);
            }
            if (dp[i - 1][1]) {
                chmax(dp[i][1], dp[i - 1][1] * 2 + max(N - cnt, cnt));
            }
        }
    }

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