POJ-3134, AOJ-1271 : Power Calculus

問題概要

今1を持っている。今持っているものから重複ありで二つ選んで(a,bとする)、新たにa+bまたはa-bを得る(ただしa-b>0に限る)。X(<1000)を得るのに必要な最小回数を求める問題。

解法

基本アイデアは反復深化。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int X;
int ANSWER;
bool exists[1<<13];
int estimate[1<<13];
int cur[13], maxi;

bool init() {
	scanf("%d", &X);
	return X > 0;
}


bool dfs(int depth) {
	if (depth + estimate[maxi] > ANSWER) {
		return false;
	}
	if (exists[X]) {
		return true;
	}
	for (int i = 0; i <= depth; ++i) {
		for (int j = 0; j <= depth; ++j) {
			const int add = cur[i] + cur[j];
			const int sub = cur[i] - cur[j];
			if (i <= j && !exists[add]) {
				int tmp = maxi;
				exists[add] = true;
				maxi = max(maxi, add);
				cur[depth + 1] = add;
				if (dfs(depth + 1)) {
					return true;
				}
				maxi = tmp;
				exists[add] = false;
			}
			if (sub > 0 && !exists[sub]) {
				exists[sub] = true;
				cur[depth + 1] = sub;
				if (dfs(depth + 1)) {
					return true;
				}
				exists[sub] = false;
			}
		}
	}
	return false;
}

int solve() {
	memset(exists, false, sizeof(exists));
	memset(estimate, 0, sizeof(estimate));
	for (int i = 1; i < 1<<13; ++i) {
		int t = i;
		for (;t < X; t <<= 1, ++estimate[i]);
	}
	exists[1] = true;
	cur[0] = 1;
	maxi = 1;
	for (ANSWER = 0; ANSWER <= 12; ++ANSWER) {
		if (dfs(0)) {
			return ANSWER;
		}
	}
	return ANSWER;
}

これだと1~1000までの答を出すのに自分のマシンでは2分かかった。
これに、作れる数はできるだけ小さい方から追加するというルールを加える。例えば5が作れる状況なのに無視して9を作ったらそれ以降5は付け加えない、みたいな。

bool dfs(int depth) {
	if (depth + estimate[maxi] > ANSWER) {
		return false;
	}
	if (exists[X]) {
		return true;
	}

	int nums[13*13];
	int n = 0;
	for (int i = 0; i <= depth; ++i) {
		for (int j = 0; j <= depth; ++j) {
			const int add = cur[i] + cur[j];
			const int sub = cur[i] - cur[j];
			if (i <= j && !exists[add] && !ignores[add]) {
				nums[n++] = add;
			}
			if (sub > 0 && !exists[sub] && !ignores[sub]) {
				nums[n++] = sub;
			}
		}
	}

	sort(nums, nums + n);
	for (int i = 0; i < n; ++i) {
		int tmp = maxi;
		exists[nums[i]] = true;
		maxi = max(maxi, nums[i]);
		cur[depth + 1] = nums[i];
		if (dfs(depth + 1)) {
			return true;
		}
		maxi = tmp;
		exists[nums[i]] = false;
		ignores[nums[i]] = true;
	}
	for (int i = 0; i < n; ++i) {
		ignores[nums[i]] = false;
	}

	return false;
}

int solve() {
	memset(exists, false, sizeof(exists));
	memset(estimate, 0, sizeof(estimate));
	memset(ignores, false, sizeof(ignores));
	for (int i = 1; i < 1<<13; ++i) {
		int t = i;
		for (;t < X; t <<= 1, ++estimate[i]);
	}
	exists[1] = true;
	cur[0] = 1;
	maxi = 1;
	for (ANSWER = 0; ANSWER <= 12; ++ANSWER) {
		if (dfs(0)) {
			return ANSWER;
		}
	}
	return ANSWER;
}

これだと1分くらい(AOJなら通る)。ここからさらに、新しい数を得るのにわざわざ2重ループ回すのではなく新しく作られた数との差分を見て更新するなどしたらもっと早くなりそう。