AOJ 3173 Hokkaido_University2 (HUPC 2020 day3-B)

きちんと細部まで詰めるのが大変かもしれない

問題へのリンク

問題概要

時刻 に座標 にいるとき、以下のいずれかの行動をすることができる。

• が偶数または が偶数のとき、時刻 に に移動する
• が奇数または が偶数のとき、時刻 に に移動する
• が偶数または が奇数のとき、時刻 に に移動する
• が奇数または が奇数のとき、時刻 に に移動する

時刻 0 に座標 にいて、座標 を目指したい。最短でたどりつく時刻はいつになるか？

制約

• 

考えたこと

、 とする。色々手を動かしていると、割と多くの場合で で到達できることがわかる。どういうときにそれができるのかを色々考えてみる。

まず一つ言えるのは、斜め 45 度方向への移動であれば、任意の時刻・座標からでも、適切にジグザグに進むことができる。

もう一つ言えるのは、

• 「 が偶数かつ が奇数」という状態を作れば、x 軸正方向に無限に進める
• 「 が奇数かつ が奇数」という状態を作れば、x 軸負方向に無限に進める
• 「 が偶数かつ が偶数」という状態を作れば、y 軸正方向に無限に進める
• 「 が奇数かつ が偶数」という状態を作れば、y 軸負方向に無限に進める

以上を踏まえると、まず かつ である場合は、適切な位置合わせを行うことで、進みたい方向に無限に進める状態になる。そしてそれによって「斜め 45 度移動で到達できる状態」を作ってあげれば、到達できる。つまり、 かつ である場合には、 で到達できる。

残りは丁寧に場合分けする。

sx = gx のとき

• が偶数のとき、初期状態から y 軸正方向には無限に進めるが、y 軸負方向に進むなら 1 秒待つ必要がある。
• が奇数のとき、初期状態から y 軸負方向には無限に進めるが、y 軸正方向に進むなら 1 秒待つ必要がある。

sy = gy のとき

• が偶数のとき、初期状態から x 軸負方向には無限に進める。 にも 1 秒で行ける。それ以外はどこかで 1 秒待つ必要がある。
• が奇数のとき、初期状態から x 軸正方向には無限に進める。 にも 1 秒で行ける。それ以外はどこかで 1 秒待つ必要がある。

#include <iostream>
using namespace std;

long long solve(long long sx, long long sy, long long gx, long long gy) {
    long long base = abs(sx - gx) + abs(sy - gy);
    if (sx == gx && sy == gy) return 0;
    else if (sx != gx && sy != gy) return base;
    else if (sx == gx) {
        if (sy % 2 == 0) {
            if (sy < gy) return base;
            else return base + 1;
        }
        else {
            if (sy > gy) return base;
            else return base + 1;
        }
    }
    else {
        if (sx % 2 == 0) {
            if (sx > gx || sx == gx - 1) return base;
            else return base + 1;
        }
        else {
            if (sx < gx || sx == gx + 1) return base;
            else return base + 1;
        }
    }
}

int main() {
    long long sx, sy, gx, gy;
    cin >> sx >> sy >> gx >> gy;
    cout << solve(sx, sy, gx, gy) << endl;
}