【AtCoder】ABC 359 C - Tile Distance 2 | 茶コーダーが解くAtCoder

実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 828

問題概要

座標平面上に $2 \times 1$ の大きさのタイルが下図のように敷き詰められている。高橋君は、始め点 $(S_x + 0.5, S_y + 0.5)$ にいて、「上下左右の方向と正の整数 $n$ を選ぶ。その方向に $n$ だけ進む」という移動を好きなだけ繰り返す。高橋君が異なるタイルを通るたび、高橋君は通行料を $1$ 支払う。高橋君が点 $(T_x + 0.5, T_y + 0.5)$ にたどり着くために支払わなければならない通行料の最小値を求めよ。

制約

入力はすべて整数。
$0 \leq S_x, S_y, T_x, T_y \leq 2 \times 10^{16}$

考察

まず、簡単のためスタートとゴールはタイルの左側の正方形にあるとして考えよう。仮に右側にあったとしても、同じタイルの移動ならば通行料はかからないので問題ない。具体的には、以下の処理を行う。

$S_x + S_y \equiv 2 = 1 \mod 2$ ならば、 $S_x$ を 1 減らす。 $T_x$ についても同様。

この処理をした後、 $dx = |S_x - S_y|, \: dy = |S_y - T_y|$ とおく。以降は、第1象限の左下から右上への移動を考える。それ以外の移動については、各移動の符号を逆にすればよい。

上図において、 $S(0.5, 0.5)$ から $G_1(9.5, 3.5)$ と $G_2(13.5, 3.5)$ への移動をそれぞれ考える。このとき、 $dx_1 = 9, dy_1 = 3, \: dx_2 = 13, dy_2 = 3$ である。

まず、 $S \rightarrow G_1$ について。図のように、上移動を繰り返しながら、タイルの左側の正方形に来たとき、現在の $x$ 座標が $T_x$ より小さいならば右移動を行う (図ではルートが重ならないように最後の方で右移動を行っているが、スタート直後から行って良い) 。こうすることで、 $x$ 軸方向の移動のコストはかからなくなり、通行料としては $dy_1$ のみを払えばよいことになる。

一方、 $S \rightarrow G_2$ については、先ほどと逆に、右移動を繰り返しながら、タイルの左側の正方形に来たとき、現在の $y$ 座標が $T_y$ より小さいならば上移動を行う。このときは、 $x$ 軸方向の移動のコストが $dy_2 + \lfloor \dfrac{dx_2 - dy_2}{2} \rfloor$ となり、 $(S_x + 0.5, S_y + 0.5) \rightarrow (T_x + 0.5, S_y + 0.5) \rightarrow (T_x + 0.5, T_y + 0.5)$ と愚直に移動するよりも 1 少なく済む。

まとめると、求める通行料の最小値 $\mathrm{cost}$ は、

$dx \leq dy \implies \mathrm{cost} = dy$
$dx > dy \implies \mathrm{cost} = dy + \lfloor \dfrac{dx - dy}{2} \rfloor$

で計算できる。

コード

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

using ll = long long;

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

int main()
{
    ll S_x, S_y, T_x, T_y;
    cin >> S_x >> S_y >> T_x >> T_y;

    S_x -= (S_y + S_x) % 2;
    T_x -= (T_y + T_x) % 2;

    ll dx = abs(T_x - S_x);
    ll dy = abs(T_y - S_y);

    cout << dy + max(0LL, dx - dy) / 2 << endl;
}