SRM 461 500pt : BuildingCities

TopCoder

問題概要

2次元平面上にN(<50)個の街がある(0< x, y < 1000)。0からN-1までの経路を考える。経路の長さをmaxT(<10^5)以下、パス上の辺の最大値をmaxD(<10^5)以下になるように新しく街を設置したい。設置しなければならない街の数の最小値を求める問題。

考えたこと

  • (当時は問題文読んだけど問題の意味が分からなかったような記憶がある)
  • 方針がすぐには見えない。
  • とりあえず到達不可能な判定は直接つないでみて大丈夫かどうかで判定できる。
  • 置く数を固定して考えたら行ける？
  • 新しく街を設置するときは2街間をつなぐ線分上に置くのが最適なはず。
  • 置く数固定しても過去にいくつあったか覚えておいたりすると情報量多すぎる。
  • というか、置く数の上限なんて高々2000*√2位なんだから意外と少ない。
  • で、街の数にこれまで置いた数の状態を付与すると状態数(50*3000)くらい？
  • あとはDijkstraするだけじゃん。
  • 辺の数は、50なので全体でO(50^2 * 3000)？これにlogがつくと結構重いような気もする。
  • 各頂点でfacetもって枝刈りする手段もあるけど、それは最後の手段にしたい。
    • 例えば各頂点でRMQ持つとかで実装できる。
  • ということで普通に書く。とはいえ距離の計算などは結構重いのでそこは前処理をかけておく。
  • 無事通った。結構実行時間長かったから、もうすこし賢いやり方があるのかも。
  • 例えば簡単な枝刈りとして、距離がmaxTを越えたら打ちきるとか、答えの最小値を覚えて置いて設置回数がそれを越えたら打ちきるとか。

practiceで通ったコード

計算量O(N^2*MAX_X * log(N*MAX_X))。

#include <vector>
#include <queue>
#include <cmath>
#include <cstdio>
using namespace std;

const int MAX_N = 50;
const int UB = 3000;
const double EPS = 1e-9;
const double INF = 1e9;

double mat[MAX_N][MAX_N];
int put[MAX_N][MAX_N];

double dist[MAX_N][UB];

struct state{
	double dist;
	int node, used;
};

//priority_queueのため逆順
bool operator<(const state& lhs, const state& rhs){
	return lhs.dist > rhs.dist;
}

struct BuildingCities {

	int findMinimumCities(int maxDirect, int maxTravel, vector <int> cityX, vector <int> cityY) {
		const int N = cityX.size();

		//距離行列の計算
		for(int i=0; i<N; i++){
			for(int j=0; j<N; j++){
				mat[i][j] = get_distance(cityX[i], cityY[i], cityX[j], cityY[j]);
			}
		}

		//i-jに辺を張るにはいくつ置く必要があるか
		for(int i=0; i<N; i++){
			for(int j=0; j<N; j++){
				put[i][j] =  (int)(mat[i][j] / maxDirect - EPS);
			}
		}

		//初期化
		for(int i=0; i<N; i++){
			fill(dist[i], dist[i] + UB, INF);
		}

		//(ノード、使用回数)でDijkstra
		priority_queue<state> que;
		que.push((state){0.0, 0, 0});
		dist[0][0] = 0;

		while(!que.empty()){
			state tp = que.top(); que.pop();
			double d = tp.dist;
			int node = tp.node, used = tp.used;

			if(d > dist[node][used]){
				continue;
			}

			for(int i=0; i<N; i++)if(used + put[node][i] < UB){
				int next_used = used + put[node][i];
				double next_d = d + mat[node][i];
				if( next_d < dist[i][next_used] ){
					que.push((state){d + mat[node][i], i, next_used});
					dist[i][next_used] = next_d;
				}
			}
		}

		//maxTravel以下で到達可能な最小値を返す
		for(int i=0; i<UB; i++){
			if(dist[N-1][i] < maxTravel + EPS){
				return i;
			}
		}

		//不可能
		return -1;

	}

	double sq(double x){
		return x*x;
	}

	double get_distance(double x1, double y1, double x2, double y2){
		return sqrt(sq(x1-x2) + sq(y1-y2));
	}
};

改善案？

  • 簡単な枝刈りを加えたもの。
  • ただし最悪計算時間が480msとあまり改善はされなかった。
		//答えを記憶しておく
		int ret = UB;

		while(!que.empty()){
			state tp = que.top(); que.pop();
			double d = tp.dist;
			int node = tp.node, used = tp.used;

			//距離、設置回数などで枝刈り
			if(d > dist[node][used] || tp.used >= ret || d > maxTravel){
				continue;
			}

			//最小値を記憶
			if(node == N-1 && d < maxTravel + EPS && used < ret){
				ret = used;
			}

			for(int i=0; i<N; i++)if(used + put[node][i] < UB){
				int next_used = used + put[node][i];
				double next_d = d + mat[node][i];
				if( next_d < dist[i][next_used] ){
					que.push((state){d + mat[node][i], i, next_used});
					dist[i][next_used] = next_d;
				}
			}
		}

		return ret == UB ? -1 : ret;