問題
整数a,b,cが与えられる。
a,b,cを２進数に変換し、a+b=cとなるように２進数の1の位置を変化させる。
このとき、式が成立する最小のcの値を求める。
そのような値が存在しない場合は-1を返す。
解き方
他の方のコードを読ませていただきました。
前の状態がわかれば現在の状態は簡単に求められるので、ｄｐが適用可能。
では、どのようにｄｐを適用したらよいかを考える。
まず、前の桁からの桁上がりと、ｘ、ｙの増分がわかれば
その桁においてｃの１の数がいくらまで可能か求められる。
よって、「aの１の数」「bの1の数」「cの1の数」「桁上がりがあるかどうか」「桁数」を引数にもち、「結果のｃの値」を値に持つｄｐを用いればよい。
計算量はO(2*30^4)となる。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
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;
FORE(i,0,n)FORE(p,0,i+1)FORE(q,0,i+1)FORE(r,0,i+1)FORE(k,0,2){
if(dp[i][p][q][r][k]==-1)continue;
FORE(nx,0,2)FORE(ny,0,2){
int bit=nx+ny+k;
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];
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
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;
FORE(i,0,n)FORE(p,0,i+1)FORE(q,0,i+1)FORE(r,0,i+1)FORE(k,0,2){
if(dp[i][p][q][r][k]==-1)continue;
FORE(nx,0,2)FORE(ny,0,2){
int bit=nx+ny+k;
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];
}
};