【1つずつ丁寧に！】ABC359 C問題〜問題の単純化〜

ABC

解説動画

動画内の説明で利用していたファイル


point
    簡単のため(もっと簡単にできるのかもしれない...)
        常に左から右に向かっていくような経路にする
        スタートもゴールも常にマスの左側となるようにする
            x座標とy座標の和の偶奇で判断可能

    スタートからゴールまで行くのに何本の線を跨ぐかを数える
        考え方: 最初に縦方向の移動を考え、そのあと横を考える
        準備:
            スタートからゴールの縦方向への移動の絶対値をdy
            スタートからゴールの横方向への移動の絶対値をdx

例1: dxがdy以下の場合 (横方向への移動が縦方向への移動以下の場合)
    (0, 0) => (5, 5)
        dx = 5
        dy = 5

    結論: dyだけの移動

例2: dxがdyより大きい時 (横方向への移動が縦方向への移動より大きい場合)
    (0, 0) => (8, 2)
        dx = 8
        dy = 2
    縦方向への移動をしながらなるべく右に移動する
        (1, 1)
        (2, 2)
            縦に移動した数だけ右に移動できる 横方向への残りの移動 = dx - dy
    あとは右へ移動する
        (4, 2)
        (6, 2)
        (8, 2)

    結論: 縦方向への移動 + 縦方向で賄いきれなかった横方向への移動で通り抜ける線の数
       = dy + (dx - dy) / 2

コード

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (n); ++i)

int main() {
    ll sx, sy, tx, ty;
    cin >> sx >> sy >> tx >> ty;

    // 常に左から右に向かっていくような経路にする
    if (tx < sx) {
        swap(sx, tx);
        swap(sy, ty);
    }

    // スタートもゴールも常にマスの左側となるようにする
    if ((sx + sy) % 2 == 1) sx--;
    if ((tx + ty) % 2 == 1) tx--;

    ll dy = abs(sy - ty);
    ll dx = abs(sx - tx);

    if (dx <= dy) {
        cout << dy << endl;
    } else {
        cout << dy + (dx - dy) / 2 << endl;
    }

    return 0;
}

コメント