ABC 117
Table of Contents
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;
}