【AtCoder】ABC 482 D - Wannabe Zombie

D - Wannabe Zombie
D - Wannabe Zombie
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
AtCoder
atcoder.jp favicon

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 766 / NoviSteps: 1Q / 配点: 400 点

問題概要

数直線上に人 1,2,…,N1,2,\dots,N の NN 人が立っており、人 ii が立っている座標は XiX_i である。

各 k=1,2,…,Nk=1,2,\dots,N について、以下の問題を解け。

時刻 00 に人 kk がゾンビになり、人 kk 以外は人のままである。 時刻 00 以降、人またはゾンビは数直線上を単位時間あたり 11 以下の速さで自由に移動できる。 ゾンビと人が同じ座標にいると、その人はゾンビになる。 全員がゾンビになる時刻として考えられる最小値を求めよ。

なおこの問題の制約下において、求める答えは整数になることが証明できる。

制約

  • 1≤N≤2×1051 \leq N \leq 2 \times 10^5
  • 0≤X1<X2<⋯<XN≤1090 \leq X_1 < X_2 < \cdots < X_N \leq 10^9
  • XiX_i は偶数
  • 入力は全て整数

考察

N=1N = 1 のときは明らかに 00 である。 以下、N≥2N \geq 2 の場合を考える。

全員がゾンビになる最小値を求めるので、各々が移動できる速さは 11 であるとしてよい。 2人が互いに速さ 11 で近づくと、距離 dd を縮めるのに必要な時間は d2\frac{d}{2} である。

また、一度ゾンビが2人になれば、それぞれが左右に移動することで感染を広げることができる。

したがって、人 kk が最初に左右どちらの人(人 k−1k-1 または人 k+1k+1)に感染させるかを考えればよい。

人 k+1k+1 に感染させる場合(右に感染させる場合)

この場合、最初のゾンビ kk が右に進み、人 k+1k+1 が左に進む。 すると、2人は時刻 t0=Xk+1−Xk2t_0=\frac{X_{k+1}-X_k}{2} に座標 mk=Xk+Xk+12m_k = \frac{X_{k}+X_{k+1}}{2} で出会って、人 k+1k+1 がゾンビになる。

その後、2人のゾンビが左右に分かれる。

時刻 t0t_0 時点でこの2人から最も離れているのは、人 11 と人 NN である。 両者も時刻 00 からそれぞれ左右に移動しているので、時刻 t0t_0 時点で、それぞれ座標 X1+t0X_1+t_0 と XN−t0X_N-t_0 にいる。

人kk が時刻 t0t_0 以降にも右に動き続けて人 NN に感染させる場合、最も早く右端に感染できる時刻は、

t0+(XN−t0)−mk2=XN+t0−mk2=XN−Xk2\begin{align*} t_0 + \frac{(X_N-t_0)- m_k}{2} &= \dfrac{X_N+t_0 - m_k}{2} \\ &= \dfrac{X_N - X_k}{2} \end{align*}

である。

一方、人 k+1k+1 が時刻 t0t_0 以降にも左に動き続けて人 11 に感染させる場合、最も早く左端に感染できる時刻は、

t0+mk−(X1+t0)2=mk−X1+t02=Xk+1−X12\begin{align*} t_0 + \frac{m_k - (X_1+t_0)}{2} &= \dfrac{m_k - X_1 + t_0}{2} \\ &= \dfrac{X_{k+1} - X_1}{2} \end{align*}

である。

したがって、この場合の答えは max⁡(XN−Xk2,Xk+1−X12)\max \left(\dfrac{X_N - X_k}{2}, \dfrac{X_{k+1} - X_1}{2}\right) である。

人 k−1k-1 に感染させる場合(左に感染させる場合)

この場合、最初のゾンビ kk が左に進み、人 k−1k-1 が左に進む。 すると、2人は時刻 t0=Xk−1−Xk2t_0=\frac{X_{k-1}-X_k}{2} に座標 mk=Xk+Xk−12m_k = \frac{X_{k}+X_{k-1}}{2} で出会って、人 k−1k-1 がゾンビになる。

前項と同様に考えると、人kk が時刻 t0t_0 以降にも左に動き続けて人 11 に感染させる場合、最も早く左端に感染できる時刻は、

t0+mk−(X1+t0)2=mk−X1+t02=Xk−X12\begin{align*} t_0 + \frac{m_k - (X_1+t_0)}{2} &= \dfrac{m_k - X_1 + t_0}{2} \\ &= \dfrac{X_k - X_1}{2} \end{align*}

である。

一方、人 k+1k+1 が時刻 t0t_0 以降にも右に動き続けて人 NN に感染させる場合、最も早く右端に感染できる時刻は、

t0+(XN−t0)−mk2=XN+t0−mk2=XN−Xk−12\begin{align*} t_0 + \frac{(X_N-t_0)- m_k}{2} &= \dfrac{X_N+t_0 - m_k}{2} \\ &= \dfrac{X_{N} - X_{k-1}}{2} \end{align*}

である。

したがって、この場合の答えは max⁡(Xk−X12,XN−Xk−12)\max \left(\dfrac{X_k - X_1}{2}, \dfrac{X_{N} - X_{k-1}}{2}\right) である。

以上をまとめると、各 k=1,2,…,Nk=1,2,\dots,N について、全員がゾンビになる時刻の最小値は、

min⁡(max⁡(XN−Xk2,Xk+1−X12),max⁡(Xk−X12,XN−Xk−12))\min \left(\max \left(\dfrac{X_N - X_k}{2}, \dfrac{X_{k+1} - X_1}{2}\right), \max \left(\dfrac{X_k - X_1}{2}, \dfrac{X_{N} - X_{k-1}}{2}\right)\right)

となる。

これはそれぞれ定数時間で計算できるので、全体として O(N)O(N) の計算量で解くことができる。

なお、実装時は k=1k = 1 と k=Nk = N の場合分けに注意すること。

実装例

CPP
1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
5. 
6.constexpr long long INFL = 1e+18;
7. 
8.using ll = long long;
9. 
10.template <typename T>
11.inline bool chmin(T& a, T b) { return ((a > b) ? (a = b, true) : (false)); }
12. 
13.// ======================================== //
14. 
15.int main()
16.{
17.    int N;
18.    cin >> N;
19. 
20.    if (N == 1) {
21.        cout << 0 << endl;
22.        return 0;
23.    }
24. 
25.    vector<ll> X(N);
26.    rep(i, 0, N) cin >> X[i];
27. 
28.    rep(k, 0, N) {
29.        ll ans = INFL;
30.        if (k > 0) {
31.            chmin(ans, max((X[k] - X[0]) / 2, (X[N - 1] - X[k - 1]) / 2));
32.        }
33.        if (k < N - 1) {
34.            chmin(ans, max((X[k + 1] - X[0]) / 2, (X[N - 1] - X[k]) / 2));
35.        }
36. 
37.        cout << ans << endl;
38.    }
39. 
40.    return 0;
41.}
https://atcoder.jp/contests/abc482/submissions/80514542
atcoder.jp
atcoder.jp favicon

実装時間: 30 分

コメント

A問題じゃなくてこっちがハロウィン問題だったのかもしれない。

関連記事