けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 359 C - Tile Distance 2 (1Q, 緑色, 350 点)

とても重たくて大変な問題。いろんな整理の仕方があると思う。

問題概要

下図のように、座標平面が 1 x 2 の長方形に区切られている。

座標  (s_{x} + 0.5, s_{y} + 0.5) から座標  (t_{x} + 0.5, t_{y} + 0.5) へと至るまでに、通過する必要のある長方形の境界の個数の最小値を求めよ。

制約

  •  0 \le s_{x}, s_{y}, t_{x}, t_{y} \le 10^{18}

考えたこと

この手の問題は、スタート地点が原点になるように平行移動できれば、考えやすくなる。その際には、ゴール地点の  y 座標が正である方が考えやすいので、適宜 swap して、あらかじめ  s_{y} \lt t_{y} となるようにすることにした。

スタートが原点になるようにするために、まず、スタートを  (0, 0) または  (1, 0) に移るように平行移動することにした。具体的には、

  • スタートとゴールの座標に対して、ともに  (1, 1) を足す
  • スタートとゴールの座標に対して、ともに  (1, -1) を足す
  • スタートとゴールの座標に対して、ともに  (-1, 1) を足す
  • スタートとゴールの座標に対して、ともに  (-1, -1) を足す
  • スタートとゴールの座標に対して、ともに  (2, 0) を足す
  • スタートとゴールの座標に対して、ともに  (-2, 0) を足す

という操作を繰り返すことを想定すればよい。最後に、スタート地点が  (1, 0) である場合には  (0, 0) としても変わらないことを利用する。

スタートからゴールへ

座標  (0, 0) からスタートして、y 座標が  t_{y} となる位置まで移動する際に、 x 方向の境界を通ることなく、到達できる x 座標を考えよう。

x 座標が  -t_{y} 以上  t_{y} + 1 以下

については、 y 方向の境界通過のみで到達できる。 t_{x} がこの範囲におさまる場合は、答えは  t_{y} となる。

 t_{x} がこの範囲におさまらない場合は、x 座標方向に通過する必要のある境界の個数を求めればよい。

コード

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

int main() {
    // スタート地点を (0, 0) にするような調整を行う
    long long sx, sy, tx, ty;
    cin >> sx >> sy >> tx >> ty;
    if (sy > ty) swap(sx, tx), swap(sy, ty);
    sx -= sy, tx -= sy, ty -= sy, sy = 0;
    if (sx % 2 == 0) tx -= sx, sx = 0;
    else tx -= (sx - 1), sx = 0;
    
    // x 軸方向の移動距離を求める
    long long dx = 0;
    if (tx > ty + 1) tx -= ty, dx = tx / 2;
    else if (tx < -ty) tx += ty, dx = (-tx + 1) / 2;
    
    // y 軸方向の移動距離 (ty) を足す
    long long res = dx + ty;
    cout << res << endl;
}