SRM 399 Div1 Medium BinarySum

問題

3つの自然数a,b,cが与えられる。これらを2進数表記にした際に、最も大きい桁数を持つ数字と桁数が同じになるように残りの2つにleading zeroを足す。これらの数字について2進数上で1と0の順番を好きに入れ替えることで新たな数字a',b',c'を作る。なおleading zeroがあってもよい。a'+b'=c'となるように入れ替えを行うとき、c'がとりうる最小の値を求めよ。不可能なら-1を返せ。

やりかた

2進数表記で、ある桁のa',b'のビットを決めれば、あとはその前の桁からの繰り上がりの有無とでc'のその桁は自然と決まる。なので、とりうるビットの計算を試して次の桁に渡すような再帰関数でとくことができる。a',b',c'それぞれの1のビット数を保持しておいて、計算に使用したらその数を1つ減らして再帰を行う。終了条件は、a',b',c'の桁数がLとすればL+1桁目まで計算した時に、a',b',c'の1のビットをすべて使いきっており、かつその状態で繰り上げがなければOKとする。

以下ソース。

ll dp[31][31][31][31][2];

class BinarySum {
public:
  int L;
  ll rec(int a, int b, int c, int k, int carry){
    if(k == L + 1)
      return a == 0 && b == 0 && c == 0 && carry == 0 ? 0 : LLINF;

    if(a < 0 || b < 0 || c < 0) return LLINF;
    
    ll &ret = dp[a][b][c][k][carry];
    if(ret != 0) return ret;

    ret = LLINF;
    if(carry == 0){
      ret = min(ret, rec(a, b, c, k + 1, 0));
      ret = min(ret, (1 << k) + rec(a - 1, b, c - 1, k + 1, 0));
      ret = min(ret, (1 << k) + rec(a, b - 1, c - 1, k + 1, 0));
      ret = min(ret, rec(a - 1, b - 1, c, k + 1, 1));
    }else{
      ret = min(ret, (1 << k) + rec(a, b, c - 1, k + 1, 0));
      ret = min(ret, rec(a - 1, b, c, k + 1, 1));
      ret = min(ret, rec(a, b - 1, c, k + 1, 1));
      ret = min(ret, (1 << k) + rec(a - 1, b - 1, c - 1, k + 1, 1));
    }
    return ret;
  }
  int rearrange(int a, int b, int c) {
    int na = __builtin_popcount(a);
    int nb = __builtin_popcount(b);
    int nc = __builtin_popcount(c);

    int ka = 31 - __builtin_clz(a);
    int kb = 31 - __builtin_clz(b);
    int kc = 31 - __builtin_clz(c);
    L = max(ka, max(kb, kc));
    memset(dp, 0, sizeof(dp));
    ll ans = rec(na, nb, nc, 0, 0);
    return ans == LLINF ? -1 : ans;
  }
};