ARC089 C : Traveling(300)
作成日：2018.01.23
最終更新日：2018.01.23
問題概要
時刻$0$に点$(0,0)$を出発し、$N$個の点$(x_i,y_i)$をそれぞれ時刻$t_i$に訪れる。
時刻が$1$進むごとにいずれかの軸に平行に$1$だけ動かなければならない時、このような点の訪れ方は可能かどうか答えよ。
制約
$1 \leq N \leq 10^5$
$0 \leq x_i , y_i \leq 10^5$
$1 \leq t_1 \lt t_2 \lt ... \lt t_N \leq 10^5$
考え方
$i$個目の条件を満たせるかどうかを考える。
その場に留まることを許された場合は、2点$(x_i,y_i)$,$(x_{i-1},y_{i-1})$間のマンハッタン距離$d$が$t_i - t_{i-1}$以下であれば良い。
但し$x_0$$= y_0$$= t_0$$= 0$である。
またその場に留まることを許されない時にも条件を満たすには、目的の点にたどり着いた後はその点に隣り合うの点を1つ選び時刻が$1$経過するごとに行き来すれば良い。
すなわち、$d$の偶奇と$t_i - t_{i-1}$の偶奇が一致していれば良い。
以上の2つの条件をすべての$i$について満たしているかを調べ、1つでも満たしていないものがあれば不可能であることが分かる。
ソースコード
マクロ等はこちら
const int MC = 100010;
int N;
int x[MC],y[MC],t[MC];
int main(){
cin >> N;
repp(i,1,N+1) cin >> t[i] >> x[i] >> y[i];
repp(i,1,N+1){
int d = abs(x[i]-x[i-1]) + abs(y[i]-y[i-1]);
int dt = t[i] - t[i-1];
if(dt < d || (dt+d)%2==1) return cout << "No" << endl , 0;
}
cout << "Yes" << endl;
return 0;
}解法まとめ
すべての$i$について2点$(x_i,y_i)$,$(x_{i-1},y_{i-1})$のマンハッタン距離$d_i$と$dt_i$$= t_i - t_{i-1}$が、$d_i \leq dt_i$かつ$d_i$と$dt_i$の偶奇が一致していればYes、そうでなければNoが答えである。(8-13行)