Codeforces #424 Div1 A. Office Keys

またしょうもないミスでレートを落とした。
http://codeforces.com/contest/830/problem/A

問題

1次元の数直線上にN人の人がおり、その座標が与えられる。
同じくK個のカギがある。

N人の人が最低1個のカギを回収して座標Pに移動したい。
N人の最大移動距離の最小値を求めよ。

解法

初期位置の座標が小さい人が、小さい座標のカギを取る方が良いのは自明だろう。
この事実をもとにすると、解法はいくつかあるようだ。

• 移動距離を二分探索する。座標の小さい人の順に、尺取り法の要領で指定された移動距離内で取れるもっとも小さい座標のカギを取るようにして条件を満たせるか判定する。O((N+K) logX) (Xは座標の最大値)
• LCS風にDP O(NK)。
• 利用するカギは連続しているはずなので、どのN個を使うかを総当たりするとO(NK)。

以下のコードは１つ目。

int N,K,P;
int A[2020],B[2020];

int ok(ll v) {
	int i,a=0;
	FOR(i,N) {
		if(a>=K) return 0;
		while(1) {
			if(a>=K) return 0;
			ll dist=abs(A[i]-B[a])+abs(B[a]-P);
			a++;
			if(dist<=v) break;
		}
	}
	return i==N;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K>>P;
	FOR(i,N) cin>>A[i];
	FOR(i,K) cin>>B[i];
	sort(A,A+N);
	sort(B,B+K);
	ll ret=(1LL<<40)-1;
	for(i=39;i>=0;i--) if(ok(ret-(1LL<<i))) ret-=1LL<<i;
	cout<<ret<<endl;
	
}

まとめ

これはすんなり。