TopCoder SRM 399 Div1 Medium BinarySum

問題

三つの正の整数a,b,cが与えられる。
それぞれを2進数での表現をx,y,zとする。

x,y,zのうち、最も桁数の多いものに合わせて、x,y,zの先頭に0をつめる。
その後で、x,y,zのそれぞれについて、桁の数字を好きに並べ替える。
並べ替えた後でleading zeroがあってもよい。
並べ替えた後、z=x+yが成り立つようにする。

このとき、zの最小値を求めよ。

制約条件

a,b,c≦2^30

方針

動的計画法。
dp[pos][xの1の数][yの1の数][zの1の数][繰り上がりがあるか]
を、下からpos桁目までみたときに、それぞれの数の1の数がx,y,zであり、繰り上がりがあるかないかが決まっているときの、pos桁目までのcの最小値とする。

これをpos+1桁目について、aを0,1どちらにするか、bを0,1どちらにするかを決めて更新していく。

ソースコード

int dp[32][32][32][32][2];

class BinarySum {
  public:
  int rearrange(int a, int b, int c) {
    int x=0,y=0,z=0,n=0;
    for(;a||b||c;n++){
      x+=a&1; y+=b&1; z+=c&1;
      a/=2; b/=2; c/=2;
    }
    memset(dp,-1,sizeof(dp));
    dp[0][0][0][0][0]=0;
    
    rep(i,n)rep(p,i+1)rep(q,i+1)rep(r,i+1)rep(k,2)if(dp[i][p][q][r][k]>=0){
      rep(nx,2)rep(ny,2){
        int bit=k+nx+ny;
        if(dp[i+1][p+nx][q+ny][r+(bit&1)][bit>>1]<0||
          dp[i+1][p+nx][q+ny][r+(bit&1)][bit>>1]>dp[i][p][q][r][k]+((bit&1)<<i))
          dp[i+1][p+nx][q+ny][r+(bit&1)][bit>>1]=dp[i][p][q][r][k]+((bit&1)<<i);
      }
    }
    return dp[n][x][y][z][0];
  }
};