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); }