AGC019 C : Fountain Walk(900)
作成日：2017.09.02
最終更新日：2017.09.02
問題概要
東西方向、南北方向それぞれ$0$から$10^8 - 1$の番号が付けられた$10^8$本の通りがある。
隣り合う2本の通りの距離はちょうど$100$メートルであり、$x$番目の南北方向の通りと$y$番目の東西方向の通りが交わる交差点は$(x,y)$と表される。
半径$10$メートルの噴水は$N$個あり、交差点$(X_i , Y_i)$に設置されている。
また同じ通りには噴水は高々1つしかなく、噴水の内部は通過できない。
交差点$(x_1 , y_1)$から$(x_2 , y_2)$に移動する時の最短の道のりの長さを求めよ。
制約
$0 \leq x_1 , y_1 , x_2 , y_2 < 10^8$
$1 \leq N \leq 2 \times 10^5$
$0 \leq X_i , Y_i < 10^8$
$i \neq j$ならば$X_i \neq X_j , Y_i \neq Y_j$
入力はすべて整数
考え方
まず噴水のある交差点とない交差点を通る時の道のりの差を考える。
その交差点で直進する場合、噴水がある時$10 \pi$メートル、噴水がない時$20$メートルであるから後者の方が短い。
またその交差点で曲がる場合、噴水がある時$5 \pi$メートル、噴水がない時$20$メートルであるから前者の方が短い。
よって可能である限り噴水のある交差点で曲がるのが良い。
次に回り道が有効であるかを考える。
同じ通りに噴水が1つしかないことから、通り1つ分回り道することで通ることができる噴水は高々1つしか増えない。
これにより少なくとも$180 + 5 \pi$だけ道のりが増加する。
その分回り道をしない場合よりも道のりが減少しなければならないが、そのためには噴水のある交差点を直進しないようになったり噴水のある交差点で曲がれるようになったりする必要がある。
しかし噴水を通る数は1つ以上は増えない(増えるのであれば回り道しなくても増やせる)から、前者と後者が同時に起こるしかない。
これも1回起こったら回り道しない場合に合流する。
以上より回り道が有効になることはないことが分かる。
最後に噴水のある交差点を何回曲がることができるか、また直進しないようにできるかを考える。
対称性より$x1 \leq x2 , y1 \leq y2$の場合のみを考えれば良い。
同じ通りに噴水は存在しないことから、通る噴水のある交差点を並べると$X,Y$ともに増加している。
よって、噴水のある交差点を通過できる最大の回数は$M=min(x2-x1,y2-y1)$とすると$M+1$回である。
また噴水のある交差点を曲がる最大の回数は、1回曲がるごとに$X,Y$両座標とも$1$増加している必要があるから$M$回である。
さらに貪欲に避けることで、直進するのは$x2$番目の南北方向の通りまたは$y2$番目の南北方向の通りの噴水のみであると決められる。
そのような位置に噴水がある時、その噴水を直進せずに済ませるために通るべき交差点があるから、そこを終点として置き換える。
繰り返し考えていくと、噴水を$M+1$回通れる時のみ遠回りしない限り避けられないことが分かる。
以上から噴水は可能な限り通れば良いことが分かる。
後は通ることのできる噴水の最大数を求めることができれば良い。
これは噴水のある南北方向の通りを始点から終点の方向に見ていった時、噴水の$Y$座標で$y1$と$y2$の間にあるものを$y2-y1$が正なら増加、負なら減少していくようにして選べる最大の個数である。
DPとして各$y$座標での答えを持つとすると、愚直にやると時間もメモリも足りない。
しかし、座標圧縮して区間maxをとれるSegment Treeを用いれば時間計算量$O(N log \: N)$、空間計算量$O(N)$で求めることができる。
ソースコード
マクロ等はこちら
Coordinate_Compression<T>
void insert(T a)
$a$を挿入
void arrange()
挿入された要素で座標圧縮を行う
int code(T a)
要素$a$に対応する番号を返す
Segment_Tree<T>
void put(int a , T b)
$a$番目の要素を$b$にする
int get(int s , int f)
区間$[s,f)$における最大値を取得
Coordinate_Compression<int> cc;
Segment_Tree<int> st;
const int MC = 200010;
const int H = 1e8 - 1;
int xx1,yy1,xx2,yy2;
int N;
int X[MC] , Y[MC];
int s[MC];
const double PI = 3.141592653589793;
int main(){
scanf("%d%d%d%d" , &xx1 , &yy1 , &xx2 , &yy2);
if(xx1 > xx2){
swap(xx1,xx2);
swap(yy1,yy2);
}
scanf("%d" , &N);
repp(i,0,N){
scanf("%d%d" , X + i , Y + i);
if(yy1 > yy2) Y[i] = H - Y[i];
s[i] = i;
cc.insert(Y[i]);
}
if(yy1 > yy2){
yy1 = H - yy1;
yy2 = H - yy2;
}
sort(s,s+N,[&](const int p , const int q){return X[p] < X[q];});
cc.insert(yy1);
cc.insert(yy2);
cc.arrange();
for(int i = 0 ; i < N && X[s[i]] <= xx2 ; ++i){
if(X[s[i]] < xx1 || Y[s[i]] < yy1 || Y[s[i]] > yy2) continue;
int co = cc.code(Y[s[i]]);
st.put(co,st.get(0,co)+1);
}
int z = st.get(0,cc.code(yy2)+1);
printf("%.12f\n" , (xx2-xx1+yy2-yy1)*100.0 - z*(20.0-5*PI) + (z==min(xx2-xx1,yy2-yy1)+1 ? 5*PI : 0));
return 0;
}解法まとめ
$x1 \leq x2 , y1 \leq y2$となるように対称移動して考える。(13-27行)
$X$座標の小さいものから見て、座標圧縮した$Y$座標それぞれにつきそれ以下の座標を考えた時の噴水を通る最大数を求めていく。(32-36行)
噴水を通る数が$min(x2-x1,y2-y1)+1$ならば噴水のある交差点を1つ直進しなければならない。(38行)