SRM 370 500pt: ConnectTheCities

TopCoder

問題概要

[0,distance(<100)]の区間を考える。この区間内に人がN(<100)人いる。人の座標を移動するのには移動させる距離に比例したコストがかかる。左端と右端には固定で人が居る。人は距離X以下にいる別の人と交信できる。左端から右端まで交信するのに必要なコストがF(<100000)以下になるようなXの最小値を求める問題。

考えたこと

  • 一目二分探索。
  • 最初に人の座標をソートしておけば、左端から順に考えられるのでよさげ。
  • dp[p] = ([0,p]をカバーするのに必要な最小コスト)とすればいけそう。
  • 書く、合わない。これじゃDAGにならないんだからそりゃそうだ。
  • dp[i][p]としてi-1人目まで処理し終えた時点で…という風に書き換える。
  • これでも合わない。何で？
  • 更新する範囲と交差の判定とDPテーブルの初期化間違えてた。修正。通った。

practiceで通ったコード

計算量O(distance^2 * log distance * N)。多分二分探索しなくてもぎりぎり通る(最悪実行時間が40msとかだった)。

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

const int MAX_R = 109;
const int MAX_N = 55;
const int INF = 1<<29;

int dp[MAX_N][MAX_R];

struct ConnectTheCities {

	int minimalRange(int distance, int funds, vector <int> position) {

		sort(position.begin(), position.end());


		//答えに関して二分探索
		//(low, high]内に答えは存在する
		int low = 0, high = distance+1;
		while(high - low > 1){
			int mid = (high + low)/2;
			if(check(mid, distance, funds, position)){
				high = mid;
			}
			else{
				low = mid;
			}
		}

		return high;
	}

	bool check(const int x, const int distance, const int funds, const vector<int>& position){
		const int N = position.size();

		//DPテーブルの初期化
		for(int i=0; i<=N; i++){
			fill(dp[i], dp[i]+(distance+1), INF);
		}
		for(int i=0; i<=x; i++){
			dp[0][i] = 0;
		}

		for(int i=0; i<N; i++){
			for(int pos = 0; pos<=distance; pos++){
				int cost = abs(pos - position[i]);
				int right = min(pos + x, distance);

				for(int j=0; j<=right; j++){
					dp[i+1][j] = min(dp[i+1][j], dp[i][pos] + cost);
				}
			}
		}

		return dp[N][distance] <= funds;
	}
};

バグを減らす工夫

  • 整数の二分探索ではかならず開区間をコメントしておく。

計算量を落とす

  • まず、明らかに配列の再利用ができるので空間計算量はO(distance)に落とせる。
  • また、ある区間の最小値が必要なDPなので、RMQを使えば計算量をO(distance * log(distance)^2 *N)に落とせる。
  • 相当頑張ればもう一段階計算量落とせそうな気もする。