【AtCoder】パ研合宿2023 第1日「SpeedRun」D - Bishop

問題

解法

に操作を行うと または に移る。

つまり、 に操作を行うと または に移る。

ここで という変数を導入すると

は操作後に または に移るといえる。

これで と を独立に考えることができるようになったため、答えは になる。

#include "my_template.hpp"
using namespace std;

void solve() {
    I64(K, X1, Y1, X2, Y2);
    i64 x = abs(X1 - X2), y = abs(Y1 - Y2);
    i64 a = abs(x + y), b = abs(x - y);
    i64 ans = ceil(a, 2 * K) + ceil(b, 2 * K);
    print(ans);
    return;
}

int main() {
    solve();
    return 0;
}

感想

無限人通していてかなり厳しい気持ちになった。

45度回転をマンハッタン距離の最大化の文脈でしか使えていないということが判明。 もうちょっと一般化して、 という変数を導入することで式変形ができるようになる手法、くらいに思っておくと良さそう。

マンハッタン距離の最大化

点 が与えられる。 点 とのマンハッタン距離の最大値について

とおくと

となり、 それぞれで最大値を求めてから大きい方を選択すれば求められるというテクニックのこと。

またこの を と のチェビシェフ距離と言う。