コンテンツにスキップ

ABC482 D - Wannabe Zombie

サイト
AtCoder
コンテスト
ABC482
問題
D - Wannabe Zombie
難易度
766

数直線上に NN 人が立っていて、人 ii の座標は XiX_i です(XiX_i は偶数で、X1<X2<⋯<XNX_1 < X_2 < \cdots < X_N)。時刻 00 に人 kk だけがゾンビになり、以降は全員が速さ 11 以下で自由に動けます。ゾンビと人が同じ座標にいると、その人はゾンビになります。各 kk について、全員がゾンビになる時刻の最小値を求める問題です(N≤2×105N \le 2 \times 10^5)。

以下、人 kk より左の人(人 1,…,k−11, \dots, k - 1)を「左側」、右の人を「右側」と呼びます。

人 jj がゾンビになったとき、その感染は「人 kk が誰かと出会い、その人が別の誰かと出会い、……」という連鎖で人 jj まで届いています。連鎖をたどって各区間の人の動きをつなげると、時刻 00 に XkX_k を出発し、速さ 11 以下で動いて、人 jj と出会う経路が 1 本できます。これを人 jj への感染経路と呼びます。

人 jj は時刻 tt に XjX_j から距離 tt 以内にいて、感染経路も XkX_k から距離 tt 以内にいます。なので、人 jj がゾンビになる時刻は ∣Xj−Xk∣/2|X_j - X_k| / 2 以上です。

k=1k = 1 なら、全員が人 11 に向かって速さ 11 で進み、人 11 は右に速さ 11 で進めば、人 jj とは時刻 (Xj−X1)/2(X_j - X_1) / 2 に出会います。上の下界と一致するので、答えは (XN−X1)/2(X_N - X_1) / 2 です。k=Nk = N のときも同じです。

次の動き方を考えます。

  • 左側の人は右に、右側の人は左に、速さ 11 で進み続ける。
  • 人 kk は左に速さ 11 で進む。
  • 人 k−1k - 1 は人 kk と出会ったら、向きを変えて右に速さ 11 で進む。

人 kk が左に進むので、左側の人 jj は時刻 (Xk−Xj)/2(X_k - X_j) / 2 にゾンビになります。人 k−1k - 1 は向きを変える前も右に速さ 11 で進んでいたので、ずっと「時刻 tt に座標 Xk−1+tX_{k-1} + t」にいます。なので、右側の人 jj は時刻 (Xj−Xk−1)/2(X_j - X_{k-1}) / 2 にゾンビになります(人 k−1k - 1 がゾンビになるより前に出会うことはありません)。全員がゾンビになる時刻は

max⁡(Xk−X1, XN−Xk−1)2\frac{\max(X_k - X_1,\ X_N - X_{k-1})}{2}

です。左右を入れ替えて、人 kk が先に右へ進む動き方では max⁡(XN−Xk, Xk+1−X1)/2\max(X_N - X_k,\ X_{k+1} - X_1) / 2 になります。答えはこの 22 つの小さいほうです。

この 22 つより早くはできないことを確かめます。人 kk が最初に誰かと出会う時刻を τ\tau、出会う人を pp とし、pp が左側だとします。人 NN への感染経路は、時刻 τ\tau まではまだ人 kk の動きそのものなので、時刻 τ\tau には人 pp と同じ座標、つまり Xp+τ≤Xk−1+τX_p + \tau \le X_{k-1} + \tau 以下の座標にいます。そこから速さ 11 以下で人 NN と出会うので、人 NN がゾンビになる時刻は (XN−Xk−1)/2(X_N - X_{k-1}) / 2 以上です。人 11 についての (Xk−X1)/2(X_k - X_1) / 2 以上という下界とあわせて、11 つ目の値以上になります。pp が右側のときも同様に 22 つ目の値以上になります。

XiX_i はすべて偶数なので、答えは整数です。計算量は O(N)O(N) です。

C++
#include "shogo-library/base/all"
void solve() {
LL(N);
VL(X, N);
rep(k, N) {
if (k == 0 || k == N - 1) {
print((X.back() - X.front()) / 2);
} else {
print(min(max(X[k] - X.front(), X.back() - X[k - 1]) / 2, max(X.back() - X[k], X[k + 1] - X.front()) / 2));
}
}
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

人は 0 始まりで、N=1N = 1 のときも k == 0 の分岐で 00 を出力します。

使用ライブラリ:cpp_include@cb82602