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

$N$ で0である桁について， $X$ を1にしたとしても $X$ と $X+N$ のビットカウントが1ずつ増加するだけである． $X$ が増えて損するだけなので， $X$ で1にする桁は $N$ も1の桁だけである．

下の桁から順に $X$ を0にするか1にするかを決定していくdpを行う． $\text{dp} \lbrack i \rbrack \lbrack j \rbrack = (N$ のうち $X$ を0/1のどちらにするか決まっていない部分を $i$ ， $i$ に対して $X$ を決めるとビットカウントが $j$ であるときの $X$ の最小 $)$ とする．

$\text{dp} \lbrack N \rbrack \lbrack j \rbrack = \text{dp} \lbrack N/2 \rbrack \lbrack j \rbrack \times 2$ ( $N$ が偶数 $\iff N$ の一番下の桁が0)
$X$ を0にするのでビットカウントの差は $j$ から変化しない．残りの $N/2$ の部分でビットカウントの差が $j$ になる最小の $X$ を求め，2倍することで $N/2$ で桁を一つ落とした分のつじつまを合わせる．
- $X$ を1にする場合
  繰り上がるので残りの $N$ の部分に1を足す．ビットカウントの差はこの操作で-1されるので $j+1$ になる．偶数の場合と同様2倍し， $X$ の一番下の桁を1にするので1を足す．
- $X$ を0にする場合
  残りの $N$ の部分は $N/2\ (\iff N$ を1ビット右シフト $)$ となる．ビットカウントの差は+1されるので $j-1$ になる．偶数の場合と同様2倍する．

このDPを全ての $0 \leq i \leq N$ について行うのは不可能である．DPの遷移に注目すると $i$ を2で割る操作ばかりであり， $N/2^i$ の付近の数しか実は関わらない．よって $i$ が取りうる値の個数は $O(\log N)$ 個しかないため，メモ化再帰等を用いることで答えを求められる．

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll, ll>;  
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
#define ALL(x) x.begin(), x.end()  
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }  
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
#ifdef DEBUG_   
#include "../program_contest_library/memo/dump.hpp"  
#else  
#define dump(...)  
#endif  
const ll INF = 1LL<<60;  
  
map<PII,ll> memo;  
ll dfs(ll n, ll diff) {  
    if(n == 0) {  
        if(diff == 0) return 0;  
        return INF;  
    }  
    if(n == 1) {  
        if(diff == 0) return 1;  
        if(diff == 1) return 0;  
        return INF;  
    }  
    if(memo.find(PII(n, diff)) != memo.end()) return memo[PII(n, diff)];  
  
    ll ret;  
    if(n%2 == 0) {  
        ret = dfs(n/2, diff) * 2;  
        if(ret >= INF) ret = INF;  
    } else {  
        ret = min(dfs((n+1)/2, diff+1)*2+1, dfs(n/2, diff-1)*2);  
        if(ret >= INF) ret = INF;  
    }  
    return memo[PII(n, diff)] = ret;  
}  
  
int main(void) {  
    ll t;  
    cin >> t;  
    while(t--) {  
        ll n;  
        cin >> n;  
  
        cout << dfs(n, 0) << endl;  
    }  
  
    return 0;  
}  
``

ferinの競プロ帳

競プロについてのメモ

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