SRM 399 Div1 Medium: BinarySum
問題
整数a,b,cが与えられる。それぞれを2進表現(no leading zeros)にしたあと桁数を一番大きいものに合わせて0で埋める。a,b,cのビットの順番を入れ替えたものをそれぞれa',b',c'としたときに、a'+b'=c'となる最小のc'を求める。解がなければ-1を返す。
制約
解法
dp[i][j][k][l][ub] := a,b,cの1のビットをそれぞれj,k,l個使用し、下の桁からの繰り上がりがubであるときの、i桁までの最小のc'。
a,bの(i+1)桁目がそれぞれ0か1かの4パターンで状態推移していく。
import java.util.*; public class BinarySum { static final int INF = Integer.MAX_VALUE; public int rearrange(int a, int b, int c) { int n = Math.max(Integer.toBinaryString(a).length(),Math.max(Integer.toBinaryString(b).length(),Integer.toBinaryString(c).length())); int x = Integer.bitCount(a); int y = Integer.bitCount(b); int z = Integer.bitCount(c); int[][][][][] dp = new int[n+1][x+2][y+2][z+2][2]; for (int i=0; i<=n; i++) for (int j=0; j<=x; j++) for (int k=0; k<=y; k++) for (int l=0; l<=z; l++) Arrays.fill(dp[i][j][k][l], INF); dp[0][0][0][0][0] = 0; for (int i=0; i<n; i++) { for (int j=0; j<=x; j++) { for (int k=0; k<=y; k++) { for (int l=0; l<=z; l++) { for (int ub=0; ub<2; ub++) { if (dp[i][j][k][l][ub] == INF) continue; for (int aBit=0; aBit<2; aBit++) { for (int bBit=0; bBit<2; bBit++) { int cBit = aBit + bBit + ub; dp[i+1][j+aBit][k+bBit][l+(cBit&1)][cBit>>1] = Math.min(dp[i+1][j+aBit][k+bBit][l+(cBit&1)][cBit>>1], dp[i][j][k][l][ub] + ((cBit&1)<<i)); } } } } } } } return dp[n][x][y][z][0] == INF ? -1 : dp[n][x][y][z][0]; } }