POJ-1011, LiveArchive-5522, UVa-307, SPOJ-STIJ, TJU-1009 : Sticks

問題概要

ある数aがb個ある。それぞれの数を分割する作業を繰り替えした結果が与えられる。aとして考えられる最小値を求める問題。

解法

探索で頑張る。
長い順に調べた方が枝刈りしやすそうであることは直感的に分かる。
最初は、長い順に元はどの木片であったか絞っていく探索を書いていたが、これだと枝刈りのタイミングが遅くなってしまいTLEしてしまう。
なので、ある長さの木片を順に構成することにする。
重複を防ぐように注意して枝刈りする。また、分岐係数や深さを抑えるために鳩ノ巣原理とかを使うと少し速くなる。
フォーラムにも書かれているけど、acceptされたコードでもTLEさせられるような入力が存在するので何だかなあという気分になる。最初書いていた方だと一瞬で終わるのに…。
SPOJ、TJUのは微妙に入力（というか問題）が変わっているらしくWAになってしまった。

最初に書いていた、TLEするコード

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <set>
#include <cstdlib>
#include <map>
using namespace std;

typedef unsigned long long hash;

const int MAX_X = 50;
const int MAX_N = 64;

int N, M, A, B;
int as[MAX_N], bs[MAX_N * MAX_X + 1], ts[MAX_N], tmps[MAX_N];
bool can_make[MAX_N + 1][MAX_N * MAX_X + 1];
hash shaker[MAX_N * MAX_X + 1];

set<hash> visited;

bool init(){
	scanf("%d", &M);
	for(int i=0; i<M; ++i){
		scanf("%d", ts+i);
	}
	return M > 0;
}

bool dfs(int d, hash h){
	if(d == N){
		return true;
	}
	if(!visited.insert(h).second){
		return false;
	}
	int cnt = 0;
	for(int i=0; i<B; ++i){
		if(!can_make[N - d][A - bs[i]]){
			cnt++;
		}
	}
	if(cnt > 0){
		return false;
	}
	cnt = 0;
	for(int i=0; i<B; ++i){
		if(!can_make[N - d - 1][A - bs[i]]){
			cnt++;
		}
	}
	if(cnt > 1){
		return false;
	}
	for(int i=0; i<B; ++i){
		if(bs[i] + as[d] == A){
			bs[i] += as[d];
			if(dfs(d + 1, h - shaker[bs[i] - as[d]] + shaker[bs[i]])){
				return true;
			}
			bs[i] -= as[d];
			return false;
		}
	}
	set<int> ss;
	for(int i=0; i<B; ++i){
		if(ss.insert(bs[i]).second){
			int nxt = bs[i] + as[d];
			if(nxt <= A && can_make[N - d - 1][A - nxt]){
				bs[i] += as[d];
				if(dfs(d + 1, h - shaker[bs[i] - as[d]] + shaker[bs[i]])){
					return true;
				}
				bs[i] -= as[d];
			}
		}
		if(!can_make[N - d - 1][A - bs[i]]){
			break;
		}
	}
	return false;
}

void pre_merge(){
	N = M;
	for(int i=0; i<N; ++i){
		as[i] = ts[i];
	}
	if(B > 1)for(;;){
		map<int, int> dict;
		for(int i=0; i<N; ++i){
			dict[as[i]]++;
		}
		int p = 0;
		bool found = false;
		for(map<int,int>::iterator itr = dict.begin(); itr != dict.end(); ++itr){
			if(itr->second <= B){
				for(int i=0; i<itr->second; ++i){
					tmps[p++] = itr->first;
				}
			}
			else{
				found = true;
				for(int i=0; i<itr->second - 2; ++i){
					tmps[p++] = itr->first;
				}
				tmps[p++] = itr->first * 2;
			}
		}
		N = p;
		for(int i=0; i<N; ++i){
			as[i] = tmps[i];
		}
		if(!found){
			break;
		}
	}
	M = N;
	for(int i=0; i<M; ++i){
		ts[i] = as[i];
	}
}

bool check(){
	pre_merge();
	int sum = accumulate(as, as + N, 0);
	sort(as, as + N);
	for(int i=1; i<=N; ++i){
		memset(can_make[i], false, sizeof(bool) * (sum + 1));
	}

	can_make[0][0] = true;
	int maxi = 0;
	for(int i=0; i<N; ++i){
		for(int j=0; j<=maxi; ++j)if(can_make[i][j]){
			can_make[i+1][j] = true;
			can_make[i+1][j + as[i]] = true;
			maxi = max(maxi, j + as[i]);
		}
	}
	reverse(as, as + N);
	memset(bs, 0, sizeof(bs));
	visited.clear();
	return dfs(0, B * shaker[0]);
}

int solve(){
	int sum = accumulate(ts, ts + M, 0);
	for(int i=1; i<=sum; i++)if(sum%i == 0){
		A = i; B = sum / A;
		if(check()){
			return i;
		}
	}
	return -1;
}

int main(){
	for(int i=0; i<=MAX_N * MAX_X; ++i){
		shaker[i] = (hash)rand() * rand() * rand() + rand();
	}
	for(;init();){
		printf("%d\n", solve());
	}

	return 0;
}

acceptされたコード

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <cstdlib>
#include <map>
#include <set>
using namespace std;

const int MAX_X = 50;
const int MAX_N = 64;

int N, A, B;
int as[MAX_N], tmps[MAX_N];
bool used[MAX_N];
set<pair<int,int> > visited;

bool init(){
	scanf("%d", &N);
	for(int i=0; i<N; ++i){
		scanf("%d", as+i);
	}
	return N > 0;
}

bool dfs(int cur, int made, int idx){
	if(made == B){
		return true;
	}

	int prev = -1;
	for(int i=idx; i<N; ++i)if(!used[i] && as[i] != prev){
		if(cur + as[i] <= A){
			used[i] = true;
			if(cur + as[i] == A){
				if(dfs(0, made + 1, 0)){
					return true;
				}
			}
			else if(dfs(cur + as[i], made, i + 1)){
				return true;
			}
			used[i] = false;
			prev = as[i];
			if(cur == 0 || cur + as[i] == A){
				return false;
			}
		}
	}

	return false;
}

void pre_merge(){
	if(B > 1)for(;;){
		map<int, int> dict;
		for(int i=0; i<N; ++i){
			dict[as[i]]++;
		}
		int p = 0;
		bool found = false;
		for(map<int,int>::iterator itr = dict.begin(); itr != dict.end(); ++itr){
			if(itr->second <= B){
				for(int i=0; i<itr->second; ++i){
					tmps[p++] = itr->first;
				}
			}
			else{
				found = true;
				for(int i=0; i<itr->second - 2; ++i){
					tmps[p++] = itr->first;
				}
				tmps[p++] = itr->first * 2;
			}
		}
		N = p;
		for(int i=0; i<N; ++i){
			as[i] = tmps[i];
		}
		if(!found){
			break;
		}
	}
}

bool check(){
	pre_merge();
	sort(as, as + N, greater<int>());
	memset(used, false, sizeof(used));
	return dfs(0, 0, 0);
}

int solve(){
	int sum = accumulate(as, as + N, 0);
	for(int i=*max_element(as, as + N); i<=sum; i++)if(sum%i == 0){
		A = i; B = sum / A;
		if(check()){
			return i;
		}
	}
	return -1;
}

int main(){
	for(;init();){
		printf("%d\n", solve());
	}

	return 0;
}