京都大学プログラミングコンテスト2015 H - Bit Count

これは解けるべきだったんや…

問題

kupc2015.contest.atcoder.jp

解法

桁 DP するだけです。

dp[n][diff][carry] = (n 桁目までの時点で X+N と X のビットカウントの差が diff で X+N のキャリーが carry となるような X の最小値)としてがんばります。

const int MAX = 60;
const ll INF = 1ll<<60;
ll dp[MAX][2*MAX][2]; // i, diff, carry

void chmin(ll& x, ll y) {
    x = min(x, y);
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--) {
        ll N;
        cin >> N;
        for (int i = 0; i < MAX; i++) for (int j = 0; j < 2*MAX; j++) for (int k = 0; k < 2; k++) dp[i][j][k] = INF;
        dp[0][MAX][0] = 0;
        for (int i = 0; i < MAX-1; i++) {
            for (int j = 0; j < 2*MAX; j++) {
                for (int k = 0; k < 2; k++) {
                    if (dp[i][j][k] == INF) continue;
                    int bit = (N>>i)&1;
                    for (ll c = 0; c < 2; c++) {
                        ll nc = c+bit+k;
                        int ch = 0;
                        if (nc%2) ch++;
                        if (c) ch--;
                        chmin(dp[i+1][j+ch][nc/2], dp[i][j][k] + (c<<i));
                    }
                }
            }
        }
        cout << dp[MAX-1][MAX][0] << endl;
    }
    return 0;
}