Codeforces #200 Div1. C. Read Time

Cの割にすんなり解けた問題。
周りも正答率高いけどね。
http://codeforces.com/contest/343/problem/C

問題

HDDは1次元のトラックの集合とし、その番号を端から順に0,1,2…とする。
このHDD上で、ヘッドがあるN個のトラック番号と、読み込みたいM個のトラック番号が与えられる。
ヘッドは時間１でトラック1個分移動できる。

全部のトラックを読み込むまでの最短時間を求めよ。

解法

先に時間を確定させてしまえば、ヘッドの位置の若い順に、まだ読んでない最少番号のトラックを読んだ後、また時間の限り大きな番号のトラックを読みにく、という処理により時間内に全トラックを読めるかはO(max(N,M) )で処理できる。

あとは最少時間を二分探索するだけ。

int N,M;
ll H[100001],P[100001];

bool okok(ll p) {
	int i,j,k;
	
	j=0;
	FOR(i,N) {
		ll t;
		if(P[j]<H[i]) {
			if(H[i]-P[j]>p) return false;
			t = max(H[i]+p-2*(H[i]-P[j]),H[i]+(p-(H[i]-P[j]))/2);
		}
		else t = H[i]+p;
		while(j<M && P[j]<=t) j++;
		if(j==M) return true;
	}
	return false;
}

void solve() {
	int f,r,i,j,k,l, x,y;
	
	cin>>N>>M;
	FOR(i,N) cin>>H[i];
	FOR(i,M) cin>>P[i];
	
	ll L=0,R=1LL<<40;
	FOR(i,60) {
		ll p=(L+R)/2;
		if(okok(p)) R=p;
		else L=p+1;
	}
	
	L=max(L-3,0LL);
	
	while(!okok(L)) L++;
	cout << L << endl;
}

まとめ

本番二分探索がさらっと思いついてよかった。