ABC482 D - Wannabe Zombie
- サイト
- AtCoder
- コンテスト
- ABC482
- 問題
- D - Wannabe Zombie
- 難易度
- 766
数直線上に 人が立っていて、人 の座標は です( は偶数で、)。時刻 に人 だけがゾンビになり、以降は全員が速さ 以下で自由に動けます。ゾンビと人が同じ座標にいると、その人はゾンビになります。各 について、全員がゾンビになる時刻の最小値を求める問題です()。
以下、人 より左の人(人 )を「左側」、右の人を「右側」と呼びます。
感染を運ぶ経路
Section titled “感染を運ぶ経路”人 がゾンビになったとき、その感染は「人 が誰かと出会い、その人が別の誰かと出会い、……」という連鎖で人 まで届いています。連鎖をたどって各区間の人の動きをつなげると、時刻 に を出発し、速さ 以下で動いて、人 と出会う経路が 1 本できます。これを人 への感染経路と呼びます。
人 は時刻 に から距離 以内にいて、感染経路も から距離 以内にいます。なので、人 がゾンビになる時刻は 以上です。
なら、全員が人 に向かって速さ で進み、人 は右に速さ で進めば、人 とは時刻 に出会います。上の下界と一致するので、答えは です。 のときも同じです。
が端でないとき
Section titled “kkk が端でないとき”次の動き方を考えます。
- 左側の人は右に、右側の人は左に、速さ で進み続ける。
- 人 は左に速さ で進む。
- 人 は人 と出会ったら、向きを変えて右に速さ で進む。
人 が左に進むので、左側の人 は時刻 にゾンビになります。人 は向きを変える前も右に速さ で進んでいたので、ずっと「時刻 に座標 」にいます。なので、右側の人 は時刻 にゾンビになります(人 がゾンビになるより前に出会うことはありません)。全員がゾンビになる時刻は
です。左右を入れ替えて、人 が先に右へ進む動き方では になります。答えはこの つの小さいほうです。
この つより早くはできないことを確かめます。人 が最初に誰かと出会う時刻を 、出会う人を とし、 が左側だとします。人 への感染経路は、時刻 まではまだ人 の動きそのものなので、時刻 には人 と同じ座標、つまり 以下の座標にいます。そこから速さ 以下で人 と出会うので、人 がゾンビになる時刻は 以上です。人 についての 以上という下界とあわせて、 つ目の値以上になります。 が右側のときも同様に つ目の値以上になります。
はすべて偶数なので、答えは整数です。計算量は です。
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 始まりで、 のときも k == 0 の分岐で を出力します。
使用ライブラリ:cpp_include@cb82602