SRM 399 500pt: BinarySum

問題概要

a,b,c(<2^30)が与えられる。a,b,cのビットの順序を入れ替えてa+b=cとなるようにしたい。最小のcを求める問題。無理なら-1を返す。

考えたこと

• ビットで最小なんだから、本質的には辞書順最小。
• すなわちgreedy。定石どおり考えると、cのビットを上から見ていってできるだけビットを使わないようにすれば良い。
• ある桁でビットを立てるかどうか考えると後は再帰的に同じ問題をとくことになる。
• つまりDP？。状態は(何桁目か、aの残りビット、bの残りビット、cの残りビット、キャリーの有無)で大体30^4。状態遷移は場合分けでO(1)。
• 場合分けが出てくるのがちょっと気にくわないけどそこまで大変な量でもないのであとは愚直に書く。
• if(!carry)をif(carry)と書いたのにずっと気づかず時間をとられたけど特にトラブルもなく通った。

practiceで通ったコード

#include <algorithm>
using namespace std;

typedef long long int64;

const int MAX_N = 32;
const int64 INF = 1LL<<50;

bool visited[MAX_N][MAX_N][MAX_N][MAX_N][2];
int64 memo[MAX_N][MAX_N][MAX_N][MAX_N][2];


struct BinarySum {

	int rearrange(int a, int b, int c) {
		int max_log = 31 - __builtin_clz(a);
		max_log = max(max_log, 31 - __builtin_clz(b));
		max_log = max(max_log, 31 - __builtin_clz(c));
		int64 ans = rec(max_log, __builtin_popcount(a), __builtin_popcount(b), __builtin_popcount(c), 0);
		return ans == INF ? -1 : (int)ans;
	}

	int64 rec(int len, int a, int b, int c, int carry){
		//基底
		if(len == -1){
			return (a==0 && b==0 && c==0 && carry==0) ? 0 : INF;
		}

		if(a < 0 || b < 0 || c < 0){
			return INF;
		}

		//メモ化処理
		if(visited[len][a][b][c][carry]){
			return memo[len][a][b][c][carry];
		}
		visited[len][a][b][c][carry] = true;

		int64& ret = memo[len][a][b][c][carry];
		ret = INF;

		//キャリー無し
		if(carry == 0){
			//この桁0
			ret = min(ret, rec(len - 1, a, b, c, 0));
			//この桁1
			ret = min(ret, (1<<len) + rec(len - 1, a, b, c-1, 1));
			ret = min(ret, (1<<len) + rec(len - 1, a-1,b,c-1, 0));
			ret = min(ret, (1<<len) + rec(len - 1, a,b-1,c-1, 0));
		}
		//キャリー有り
		else{
			//この桁0
			ret = min(ret, rec(len - 1, a-1, b-1, c, 0));
			ret = min(ret, rec(len - 1, a-1, b, c, 1));
			ret = min(ret, rec(len - 1, a, b-1, c, 1));

			//この桁1
			ret = min(ret, (1<<len) + rec(len - 1, a-1, b-1, c-1, 1));
		}

		return ret;
	}
};