Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-02-15SRM399 (Practice)

SRM 399 BinarySum

|  SRM 399 BinarySum - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 399 BinarySum - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=8711

コーディングフェーズ

  • はじめは数学的に解こうとした
    • 1のビットをどう動かせば最小になるかを考えるなどした
    • 難しい・・・
  • 30分後、ふと探索という考えが頭をよぎった
    • これ[桁][Aで使った1の数][Bで使った1の数][足した結果の1の数][繰上げフラグ] のDPでいけるじゃん
    • 実装

import java.util.Arrays;

public class BinarySum {

	public int rearrange(int a, int b, int c) {
		int an = Integer.bitCount(a);
		int bn = Integer.bitCount(b);
		int cn = Integer.bitCount(c);
		int maxdigit = 0;
		int[] cp = new int[]{a, b, c};
		for (int i = 0 ; i < 3 ; i++) {
			int digit = 0;
			while (cp[i] > 0) {
				cp[i] /= 2;
				digit++;
			}
			maxdigit = Math.max(maxdigit, digit);
		}
		if (an + bn < cn) {
			return -1;
		}
		
		int maxvalue = (1<<maxdigit)-1;
		long md = ((1L<<an)-1) + ((1L<<bn)-1);
		int mindigit = Long.bitCount(md);
		if (mindigit == cn) {
			if (md <= maxvalue) {
				return (int)md;
			} else {
				return -1;
			}
		}
		
		int ma = 32;
		long[][][][][] dp = new long[ma][ma][ma][ma][2];
		for (int i = 0 ; i < ma ; i++) {
			for (int j = 0 ; j < ma ; j++) {
				for (int k = 0 ; k < ma ; k++) {
					for (int l = 0 ; l < ma ; l++) {
						Arrays.fill(dp[i][j][k][l], Integer.MAX_VALUE);
					}
				}
			}
		}
		dp[0][0][0][0][0] = 0;
		for (int now = 0 ; now < maxdigit ; now++) {
			for (int oa = 0 ; oa <= an ; oa++) {
				for (int ob = 0 ; ob <= bn ; ob++) {
					for (int res = 0 ; res <= cn ; res++) {
						for (int carry = 0 ; carry <= 1 ; carry++) {
							if (dp[now][oa][ob][res][carry] != Integer.MAX_VALUE) {
								long base = dp[now][oa][ob][res][carry];
								// 0 + 0
								dp[now+1][oa][ob][res+carry][0] = Math.min(dp[now+1][oa][ob][res+carry][0], base + (carry<<now));
								
								
								// 1 + 0
								if (carry == 0) {
									dp[now+1][oa+1][ob][res+1][0] = Math.min(dp[now+1][oa+1][ob][res+1][0], base + (1<<now));
								} else {
									dp[now+1][oa+1][ob][res][1] = Math.min(dp[now+1][oa+1][ob][res][1], base);
								}

								// 0 + 1
								if (carry == 0) {
									dp[now+1][oa][ob+1][res+1][0] = Math.min(dp[now+1][oa][ob+1][res+1][0], base + (1<<now));
								} else {
									dp[now+1][oa][ob+1][res][1] = Math.min(dp[now+1][oa][ob+1][res][1], base);
								}
								
								
								// 1 + 1
								if (carry == 0) {
									dp[now+1][oa+1][ob+1][res][1] = Math.min(dp[now+1][oa+1][ob+1][res][0], base);
								} else {
									dp[now+1][oa+1][ob+1][res+1][1] = Math.min(dp[now+1][oa+1][ob+1][res+1][1], base + (1<<now));
								}
							}
						}
					}
				}
			}
		}
		return (dp[maxdigit][an][bn][cn][0] != Integer.MAX_VALUE) ? (int)dp[maxdigit][an][bn][cn][0] : -1;
	}

}