AtCoder ARC #120 : E - 1D Party

てこずったけどどうにか本番に解けた。
https://atcoder.jp/contests/arc120/tasks/arc120_e

問題

N人の人が数直線上に順に並んでいる。
各人秒速1以下で、数直線上を両方向に移動できるとする。

ここで、各人が両隣の人と座標を一致する瞬間が1度でもあるように移動させることを考える。
かかる時間の最小値はいくつか。

解法

二分探索で解く。
すなわち、仮の解をtとし、t秒以内に条件を満たす移動が可能かを考えてみる。

人の区間[L,R]において、前半何人かが最初数直線の正の方向、後半何人かが負の方向に移動したとする。
各人、移動方向の人と出会ったら逆向きに折り返すと考えよう。
そこを蟻本のAntで出てきたように、折り返すのではなくすれ違うと考えよう。

[L,R]のうち、数直線正の方向に動く人が[L,M]で、負の方向に動く人が[M+1,R]とする。
また、次の区間[L2,R2]に対し、同様に正の方向に動く人が[L2,M2]で、負の方向に動く人が[M2+1,R2]とする。
この時、(折り返さずすれ違うと考えると)M番の人と(M2+1)番の人が時間t以内に合流できるなら、(M+1)～M2番の人は左右どちらに移動してもよい。

累積和を使いながら、このように左右どちらに移動できるか選択肢のある人を列挙し、全領域をカバーできるか判定しよう。

int N;
ll A[202020];

int dp[202020];

int ok(ll v) {
	int i;
	ZERO(dp);
	dp[0]=1;
	dp[1]=-1;
	FOR(i,N-1) {
		if(i) dp[i]+=dp[i-1];
		if(dp[i]==0) continue;
		
		int x=lower_bound(A+i,A+N,A[i]+2*v+1)-A;
		x--;
		if(x==N-1) return 1;
		if(i==0) {
			dp[1]++;
			dp[x]--;
		}
		else if(x>i+2) {
			dp[i+2]++;
			dp[x]--;
		}
		
	}
	return 0;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	ll mi=1LL<<29;
	for(i=28;i>=0;i--) if(ok(mi-(1<<i))) mi-=1<<i;
	
	
	cout<<mi<<endl;
	
}

まとめ

細かい境界条件を詰めるのに手間取った。
ミスが多いのはもったいないが、まぁレート増だったし良しとするか。