POJ-2442: Sequence

keyword

分割統治法　C++

問題概要

長さN(<2000)の数列がM(<200)個ある。それぞれの数列から一つずつ選んで和を作る。作ることのできる和(取ってきた場所が違うなら値が同じでもよい)のうち、小さい方から順にN個を出力する問題。

解法

分割統治法で処理する。各区間に対して、和を小さい方からN個返すようにする。mergeの部分は、N*(1/1 + 1/2 + 1/3 + 1/4 + ... + 1/N)で処理できる。
最初はpriority_queueを使ってdijkstraっぽく書いていたけど、やっぱりコンテナにvectorを突っ込むのはコストが大きい(回転などの操作の処理が重くなる)のでTLEした。
分割統治法。計算量O(M*log(M)*N*log(N))。

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

const int MAX_M = 109;
const int MAX_N = 2009;

vector<int> ass[MAX_M];
vector<int> ans;
int N, M;

//[a, b)
vector<int> rec(int a, int b){
	if(b-a==1){
		return ass[a];
	}
	int mid = (a+b)/2;
	vector<int> as = rec(a,mid);
	vector<int> bs = rec(mid,b);
	vector<int> cands;
	cands.reserve(16000);
	for(int i=0; i<N; i++){
		for(int j=0;(i+1)*(j+1) <= N; j++){
			cands.push_back(as[i] + bs[j]);
		}
	}
	sort(cands.begin(), cands.end());
	cands.erase(cands.begin() + N, cands.end());
	return cands;
}

void print(){
	for(int i=0; i<N; i++){
		printf("%d%c",ans[i], i==N-1?'\n':' ');
	}
}

int main(){
	int T;
	for(scanf("%d",&T); T--; ){
		scanf("%d%d",&M,&N);
		for(int i=0; i<M; i++){
			ass[i].clear();
			ass[i].reserve(N);
			for(int j=0; j<N; j++){
				int x;
				scanf("%d",&x);
				ass[i].push_back(x);
			}
			sort(ass[i].begin(), ass[i].end());
		}
		ans = rec(0,M);
		print();
	}
	return 0;
}

Dijkstraっぽい解法。計算量O(M^2*N*log(N*M))。O(M*N*log(N*M))でないことに注意。TLEする。

#include <cstdio>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;

typedef pair<int, vector<int> > state;
typedef unsigned long long ul;

const int MAX_M = 109;
const int MAX_N = 2009;

vector<int> ass[MAX_M];
vector<int> ans;
int N, M;

inline ul hash(vector<int>& xs){
	ul ret = 0, base = 1;
	for(int i=0; i<M; i++){
		ret += (ul)xs[i] * base;
		base *= 1000000007;
	}
	return ret;
}

void solve(){
	priority_queue<state, vector<state>, greater<state> > Q;
	set<pair<int, ul> > visited;
	{
		int sum = 0;
		vector<int> ids;
		for(int i=0; i<M; i++){
			ids.push_back(0);
			sum += ass[i][0];
		}
		Q.push( make_pair(sum, ids) );
		visited.insert( make_pair(sum, hash(ids)) );
	}
	while(!Q.empty() && (int)ans.size() < N){
		state tp = Q.top(); Q.pop();
		int sum = tp.first;
		ans.push_back(sum);
		vector<int> ids = tp.second;
		for(int j=0; j<M; j++){
			if(ids[j] < N-1){
				int tmp = ids[j];
				while(ids[j] < N-1 && ass[j][tmp] == ass[j][++ids[j]]){
					ans.push_back(sum);
				}
				if(ids[j] < N){
					state ns(sum + ass[j][ids[j]] - ass[j][tmp], ids);
					if(visited.insert( make_pair(ns.first, hash(ids)) ).second){
						Q.push(ns);
					}
				}
				ids[j] = tmp;
			}
		}
	}
}

void print(){
	for(int i=0; i<N; i++){
		printf("%d%c",ans[i], i==N-1?'\n':' ');
	}
}

int main(){
	int T;
	for(scanf("%d",&T); T--; ){
		scanf("%d%d",&M,&N);
		for(int i=0; i<M; i++){
			ass[i].clear();
			ass[i].reserve(N);
			for(int j=0; j<N; j++){
				int x;
				scanf("%d",&x);
				ass[i].push_back(x);
			}
			sort(ass[i].begin(), ass[i].end());
		}
		ans.clear();
		solve();
		print();
	}
	return 0;
}