【AtCoder】ABC 419 C - King's Summit | 緑コーダーが解くAtCoder

配点: 300 点 / 実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 259 / NoviSteps: 3Q

問題概要
制約
考察
実装例
コメント

問題概要

$10^9 \times 10^9$ のグリッドがあり、このグリッドの上から $i$ 番目、左から $j$ 番目のマスをマス $(i, j)$ と表す。

グリッド上には $N$ 人の人がおり、はじめ時刻 $t = 0$ において $i$ 人目の人はマス $(R_i, C_i)$ にいる。それぞれの人は、時刻 [tex: t =1, 2, 3, \dots$ に以下のような移動をすることができる。

その場に留まるか、8近傍のマスに移動する。ただし、グリッドの外側に出ることはできない。また、移動には時間がかからないものとする。

$N$ 人が全員同じマスに集まる時刻として考えられる最小値を求めよ。

制約

$1 \leq N \leq 2 \times 10^5$
$1 \leq R_i, C_i \leq 10^9$
入力される値はすべて整数

考察

移動は8近傍に対して行えるので、縦方向と横方向それぞれ独立に考えることができる。

マス $(R_T, C_T)$ へ時刻 $t$ までに $N$ 人を集めることにする。このとき、縦方向に注目すると、全ての $i$ に対して

$\max(|R_i - R_T|) \leq t$

が成り立っている必要がある(チェビシェフ距離の1次元バージョン)。

$R_T$ は全ての $i$ に対して閉区間 $[R_i - t, R_i + t$ ] に含まれなければならない。これら $N$ 個の共通部分は $[ \underset{i}{\max} R_i - t, \underset{i}{\min} R_i + t$ ] と表せ、この区間が存在する条件は

$\begin{align*} \underset{i}{\max} R_i - t \leq \underset{i}{\min} R_i + t \iff \underset{i}{\max} R_i - \underset{i}{\min} R_i \leq 2t \end{align*}$

と書くことができる。同様の議論を横方向にも行うことができるので、

$\left\{ \begin{array}{ll} \underset{i}{\max} R_i - \underset{i}{\min} R_i \leq 2t \\ \underset{i}{\max} C_i - \underset{i}{\min} C_i \leq 2t \end{array} \right.$

であり、 $\max(|R_i - R_T|, \, |C_i - C_T|) \leq t$ であることを踏まえながら2式をまとめると

$\begin{align*} \frac{\max(\underset{i}{\max} R_i - \underset{i}{\min} R_i, \, \underset{i}{\max} C_i - \underset{i}{\min} C_i)}{2} \leq t \end{align*}$

となる。

これを満たす最小の整数 $t$ は、

$\begin{align*} t = \left\lceil \frac{\max(\underset{i}{\max} R_i - \underset{i}{\min} R_i, \, \underset{i}{\max} C_i - \underset{i}{\min} C_i)}{2} \right\rceil \end{align*}$

である。

あとはこれを実装するだけ。

実装例

#include <bits/stdc++.h>
using namespace std;

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

constexpr long long INFL = 1e+18;

using ll = long long;

template <class T1, class T2>
inline auto div_ceil(T1 a, T2 b)
{
    if (b < 0)
        a *= -1, b *= -1;
    if (a <= 0)
        return a / b;
    else
        return (a - 1) / b + 1;
}
template <typename T>
inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); }
template <typename T>
inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); }

// ======================================== //

int main()
{
    int N;
    cin >> N;
    ll minR = INFL, maxR = -INFL, minC = INFL, maxC = -INFL;
    rep(i, 0, N)
    {
        ll R, C;
        cin >> R >> C;
        chmin(minR, R);
        chmax(maxR, R);
        chmin(minC, C);
        chmax(maxC, C);
    }

    ll dR = maxR - minR, dC = maxC - minC;

    cout << div_ceil(max(dR, dC), 2LL) << endl;

    return 0;
}