t8m8-mem8

競プロとか、学んだことを書いていきます。

SRM 399 Div1 Medium: BinarySum

問題

整数a,b,cが与えられる。それぞれを2進表現(no leading zeros)にしたあと桁数を一番大きいものに合わせて0で埋める。a,b,cのビットの順番を入れ替えたものをそれぞれa',b',c'としたときに、a'+b'=c'となる最小のc'を求める。解がなければ-1を返す。

制約

 1 {\leq} a,b,c {\leq} {2}^{30}

解法

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];
    }
}