ABC178E - Dist Max

E - Dist Max

考え方

$i,j$を含んだ式で2重ループだとTLEする問題．

典型的なパターンとして，①$|x_{i} - x_{j}| + |y_{i} - y_{j}| = X$となる$X$を振る，②$i,j$を式変形で分離してループを1つにする，が考えられる．

①は$1\leq x_{i}, y_{i}\leq 10^{9}$だからTLEする．

②を考える．絶対値の問題では

• $|x| = \max(x, -x)$
• $x \geq y$とした上で処理することにすれば$|x - y| = x - y$

という関係式が基本．

公式解説のように絶対値にまとめられることに気づかなくても，4項考えれば良い．つまり，$i,j$を分離するように式変形をすれば

\begin{aligned}
& |x_{i} - x_{j}| + |y_{i} - y_{j}| \\
&= \max(x_{i} - x_{j}, -x_{i} + x_{j}) \\
& \quad
+ \max(y_{i} - y_{j}, -y_{i} + y_{j}) \\
&= \max\Bigl((x_{i} + y_{i}) - (x_{j} + y_{j}) \\
& \qquad \qquad
, (x_{i} - y_{i}) - (x_{j} - y_{j}) \\
& \qquad \qquad
, -(x_{i} - y_{i}) + (x_{j} - y_{j}) \\
& \qquad \qquad
, -(x_{i} + y_{i}) + (x_{j} + y_{j})\Bigr)
\end{aligned}

より

\begin{aligned}
&\max_{i,j} \Bigl( |x_{i} - x_{j}| + |y_{i} - y_{j}| \Bigr) \\
&= \max\Bigl(\textcolor{red}{\max_{i}}(x_{i} + y_{i}) - \textcolor{blue}{\min_{i}}(x_{i} + y_{i}) \\
& \qquad \qquad
, \textcolor{red}{\max_{i}}(x_{i} - y_{i}) - \textcolor{blue}{\min_{i}}(x_{i} - y_{i}) \\
& \qquad \qquad
, -\textcolor{blue}{\min_{i}}(x_{i} - y_{i}) + \textcolor{red}{\max_{i}}(x_{i} - y_{i}) \\
& \qquad \qquad
, -\textcolor{blue}{\min_{i}}(x_{i} + y_{i}) + \textcolor{red}{\max_{i}}(x_{i} + y_{i})\Bigr) \\
&=\max\Bigl( \max_{i}(x_{i} + y_{i}) - \min_{i}(x_{i} + y_{i}), \\
& \qquad \qquad \qquad
\max_{i}(x_{i} - y_{i}) - \min_{i}(x_{i} - y_{i}) \Bigr)
\end{aligned}

となる．

別解

$x_{i} \geq x_{j}$とした上で$i,j$を分離するように式変形をすれば

\begin{aligned}
& |x_{i} - x_{j}| + |y_{i} - y_{j}| \\
&= x_{i} - x_{j} + |y_{i} - y_{j}| \\
&= x_{i} - x_{j} + \max(y_{i} - y_{j}, -y_{i} + y_{j}) \\
&= \max\Bigl( (x_{i} + y_{i}) - (x_{j} + y_{j}), \\
& \qquad \qquad \qquad
(x_{i} - y_{i}) - (x_{j} - y_{j}) \Bigr) \\
\end{aligned}

なので，

\begin{aligned}
&\max_{i,j} \Bigl( |x_{i} - x_{j}| + |y_{i} - y_{j}| \Bigr) \\
&=\max_{\substack{i,j \\ (x_{i} \geq x_{j})}} \Bigl( |x_{i} - x_{j}| + |y_{i} - y_{j}| \Bigr) \\
&=\max_{\substack{i,j \\ (x_{i} \geq x_{j})}} \Bigl( x_{i} - x_{j} + |y_{i} - y_{j}| \Bigr) \\
&=\max_{i,j} \Bigl( x_{i} - x_{j} + |y_{i} - y_{j}| \Bigr) \\
&=\max\Bigl(\max_{i,j}[(x_{i} + y_{i}) - (x_{j} + y_{j})], \\
& \qquad \qquad \qquad
\max_{i,j}(x_{i} - y_{i}) - (x_{j} - y_{j})] \Bigr) \\
&=\max\Bigl( \max_{i}(x_{i} + y_{i}) - \min_{i}(x_{i} + y_{i}), \\
& \qquad \qquad \qquad
\max_{i}(x_{i} - y_{i}) - \min_{i}(x_{i} - y_{i}) \Bigr)
\end{aligned}

となる．