SRM 367 500pt: DeviceProgramming

TopCoder

問題概要

一列にデータが並んでいて、互いに素な区間がN(<50)個ある。区間の長さや初期位置は10^9以下である。この区間全てをいくつかの小区間でカバーする。ひとつの小区間にかかるコストは区間の長さ+overhead(<1000)で、ひとつの小区間のコストはmaxPacketSizeを越えてはいけない。必要な最小コストを求める問題。

考えたこと

  • 貪欲?いや、区間を短く打ちきることができるから違うか。
  • 長すぎる区間は意味が無いので2*maxPacketSize以下に落としても大丈夫そう。
  • こうしたら座標圧縮と合わせてDPで解けそう。
  • でも座標圧縮+DPとか絶対バグ埋め込む自信がある。
  • とはいえ他の解法も思い浮かばないので仕方なく座標圧縮+DPを書き始める。
  • 区間を閉区間にするか半開区間にするかあやふやなまま書いていた。
    • やっぱり半開区間の方が書きやすかった。

practiceで通ったコード

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

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

typedef long long int64;

const int64 INF = 1LL<<61;


struct DeviceProgramming {

	int64 minBytes(vector <int> offset, vector <int> size, const int max_packet_size, const int overhead) {
		const int N = offset.size();
		const int max_data_size = max_packet_size - overhead;

		int64 ret = 0;

		//データをまとめる 開区間[from, to)
		vector< pair<int64,int64> > datas;
		for(int i=0; i<N; i++){
			datas.push_back( make_pair(offset[i], offset[i]+size[i]) );
		}
		sort(datas.begin(), datas.end());

		//全てのデータを長さ大体3000以下にする。
		for(int i=0; i<N; i++){
			int len = datas[i].second - datas[i].first;
			if(len > 2000){
				int64 packet_count = (len - 2000)/max_data_size;
				int64 total_packet_size = max_packet_size * packet_count;
				int64 total_data_size = max_data_size * packet_count;
				ret += total_packet_size;
				datas[i].second -= total_data_size;
				for(int j=i+1; j<N; j++){
					datas[j].first -= total_data_size;
					datas[j].second -= total_data_size;
				}
			}
		}


		//座標圧縮
		vector<int64> compress;
		vector<int> attributes;
		for(int i=0; i<N; i++){
			for(int64 k=datas[i].first; k<datas[i].second; k++){
				compress.push_back(k);
				attributes.push_back(i);
			}
		}
		//ソートとかはしなくてよい

		//DPテーブルの初期化
		const int M = compress.size();
		vector<int64> dp(M+1,INF);
		dp[0] = 0;

		//DP
		for(int i=0; i<M; i++){
			//現在位置の情報
			int color = attributes[i];
			int cur = compress[i];

			int next_longest_index = get_index(compress, cur + max_data_size - 1);

			//全部使う
			if(next_longest_index >= 0){
				dp[next_longest_index + 1] = min(dp[next_longest_index + 1], dp[i] + max_packet_size);
			}

			//キリの良いところまで使う
			for(int j=color; j<N; j++)if( datas[j].second - cur <= max_data_size){
				int next_index = get_index(compress, datas[j].second - 1) + 1;
				dp[next_index] = min(dp[next_index], dp[i] + (datas[j].second - cur) + overhead);
			}
		}

		ret += dp.back();
		return ret;
	}

	int get_index(const vector<int64>& compress, int64 val){
		if(!binary_search(compress.begin(), compress.end(), val)) return -1;
		return distance(compress.begin(), lower_bound(compress.begin(), compress.end(), val));
	}

};

計算量を下げる

座標圧縮とか面倒くさいことしなくても、ある区間の途中は必ず埋まるんだからdp[i] = (i-1番目までをカバーする最小値)とすればdp[i]からdp[i+1],..,dp[N]までの遷移を考えるとO(N^2)で解ける。