AtCoder Regular Contest #001 D : レースゲーム

問題概要

(sx,0)から(gx,N) (N<2*10^5)までの最短距離が知りたい。ただし、任意のiについてy=iのときはl[i]<=x<=r[i]でなくてはならない。

解法

愚直に可視グラフ作ってからDPするのはO(N^3)。少し工夫を加えるとO(N^2)まではすぐに落ちる。
想定解っぽいのは適宜メモ化しながら下から順に計算するらしい。
自分は左側と右側の壁で交互に凸包つくって、凸包の頂点は必ず通ることを利用して再帰的に解いた。イメージとしては、スタートとゴールの間に紐をピンと張って、左右の壁で押し合う、みたいな…。計算量が怪しいけど実は怪しくなくてただしいのかもしれない。

acceptしたかったコード

実際は枝刈りを付け加えてC++で書き直して出した。

import std.stdio;
import std.math;
import std.algorithm;

class Point{
	long x, y;
	this(long x, long y){
		this.x = x;
		this.y = y;
	}
	
	Point opSub(Point p){
		return new Point(x - p.x, y - p.y);
	}
	
	override bool opEquals(Object o){
		return x == (cast(Point)o).x && y == (cast(Point)o).y;
	}
	
}

long iprod(Point a, Point b){
	return a.x * b.x + a.y * b.y;
}

long oprod(Point a, Point b){
	return a.x * b.y - b.x * a.y;
}

long sq(long x){
	return x * x;
}

long abs2(Point a){
	return sq(a.x) + sq(a.y);
}

real getDistance(Point a){
	return sqrt(cast(real)abs2(a));
}

real getDistance(Point a, Point b){
	return getDistance(a - b);
}

int ccw(Point a, Point b, Point c){
	auto nb = b - a, nc = c - a;
	if( oprod(nb, nc) > 0 ){
		return +1;
	}
	if( oprod(nb, nc) < 0 ){
		return -1;
	}
	if( iprod(nb, nc) < 0 ){
		return +2;
	}
	if( abs2(nb) < abs2(nc) ){
		return -2;
	}
	return 0;
}

int N, start, goal;
Point[] ls, rs;
int[] lx, rx;

void init(){
	scanf("%d%d%d", &N, &start, &goal);
	
	ls = new Point[](N + 1);
	rs = new Point[](N + 1);
	lx = new int[](N + 1);
	rx = new int[](N + 1);
	for(int i=0; i<=N; ++i){
		scanf("%d%d", &lx[i], &rx[i]);
		ls[i] = new Point(lx[i], i);
		rs[i] = new Point(rx[i], i);
	}
	
}

Point[] convexHullLeft(Point[] ps){
	int n = cast(int)ps.length;
	int k = 0;
	Point[] ret = new Point[](n);
	for(int i=0; i<n; ++i){
		for(;k>1 && oprod(ret[k-1] - ret[k-2], ps[i] - ret[k-1]) <= 0; --k){}
		ret[k++] = ps[i];
	}
	return ret[0..k];
}

Point[] convexHullRight(Point[] ps){
	int n = cast(int)ps.length;
	int k = 0;
	Point[] ret = new Point[](n);
	for(int i=0; i<n; ++i){
		for(;k>1 && oprod(ret[k-1] - ret[k-2], ps[i] - ret[k-1]) >= 0; --k){}
		ret[k++] = ps[i];
	}
	return ret[0..k];
}

real calcLeft(int from, int to, bool fin = false){
	if(to - from == 1){
		return getDistance(ls[from], ls[to]);
	}
	
	auto es = convexHullLeft(ls[from..to+1]);
	
	if(fin && es.length == 2){
		return getDistance(es[0], es[1]);
	}
	else{
		real ans = 0.0;
		for(int i=0; i<es.length-1; ++i){
			int y1 = cast(int)es[i].y, y2 = cast(int)es[i+1].y;
			ls[y1] = rs[y1] = es[i];
			ls[y2] = rs[y2] = es[i+1];
			ans += calcRight(y1, y2);
		}
		return ans;
	}
}

real calcRight(int from, int to){
	if(to - from == 1){
		return getDistance(rs[from], rs[to]);
	}
	
	auto es = convexHullRight(rs[from..to+1]);
	
	if(es.length == 2){
		return getDistance(es[0], es[1]);
	}
	else{
		real ans = 0.0;
		for(int i=0; i<es.length-1; ++i){
			int y1 = cast(int)es[i].y, y2 = cast(int)es[i+1].y;
			ls[y1] = rs[y1] = es[i];
			ls[y2] = rs[y2] = es[i+1];
			ans += calcLeft(y1, y2, true);
		}
		return ans;
	}
}

real solve(){
	ls[0] = rs[0] = new Point(start, 0);
	ls[N] = rs[N] = new Point(goal, N);
	return calcLeft(0, N);
}

void main(){
	init;
	writefln("%.12f", solve);
}