TopCoder SRM 718 Div1 Medium CircleCity、Div2 Hard ChainCity

これも定番っぽいのだが…。
https://community.topcoder.com/stat?c=problem_statement&pm=14541
https://community.topcoder.com/stat?c=problem_statement&pm=14643

問題

1次元の軸上でN個の頂点があり、互いの距離が与えられる。
Div1は円周上、Div2は直線上に頂点がある。
点の間を移動する際、速度が1であるとするとき、頂点間の移動時間の最大値を最小化したい。

ここで、K個の瞬間移動装置を任意に配置できるとする。
これらの装置間は瞬時に移動可能である。

瞬間移動装置を最適に配置したとき、頂点間の移動時間の最大値を最小化せよ。

解法

まずDiv2から。
N個の頂点をK個のセグメントで覆うことを考える。
各セグメントの中心に装置を配置すれば、求める移動時間は最大セグメント長に一致する。
よって、あとは最大セグメント長を二分探索し、K個のセグメントで全頂点を覆えるか判定すればよい。

Div1の場合頂点が円形に配置されているため、各頂点が1つめのセグメントの端点である場合を総当たりし、同様に判定しよう。

class CircleCity {
	public:
	int N;
	ll X[2020];
	int ok(ll v) {
		int i,num=0;
		ll range=-1;
		FOR(i,N) {
			if(X[i]>range) {
				range=X[i]+v;
				num++;
			}
		}
		return num;
	}
	
	int findMin(vector <int> dist, int k) {
		int i,j;
		
		ll mi=1LL<<50;
		N=dist.size();
		FOR(i,N) {
			FOR(j,N-1) X[j+1]=X[j]+dist[j];
			
			rotate(dist.begin(),dist.begin()+1,dist.end());
			ll ret=(1LL<<50)-1;
			for(j=49;j>=0;j--) if(ok(ret-(1LL<<j))<=k) ret -= 1LL<<j;
			mi=min(mi,ret);
		}
		return mi;
		
		
		
	}
}

int N;
ll X[2020];

class ChainCity {
	public:
	int ok(ll v) {
		int i,num=0;
		ll range=-1;
		FOR(i,N) {
			if(X[i]>range) {
				range=X[i]+v;
				num++;
			}
		}
		return num;
	}
	
	int findMin(vector <int> dist, int k) {
		N=dist.size()+1;
		int i;
		FOR(i,N-1) X[i+1]=X[i]+dist[i];
		
		ll ret=(1LL<<50)-1;
		for(i=49;i>=0;i--) if(ok(ret-(1LL<<i))<=k) ret -= 1LL<<i;
		return ret;
		
	}
}

まとめ

Codeforcesで多そうな問題。