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

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

AtCoder ABC 184 C - Super Ryuma (茶色, 300 点)

これ難しいと思った!
あと、どうやら (1, 1, 1, 6) を 3 回にする嘘解法が AC になったらしい

問題概要

以下の動きのできる駒がある。駒をマス  (a, b) からマス  (c, d) へ移動させるのに必要な手数の最小値を求めよ。

f:id:drken1215:20201122221633p:plain

制約

  •  1 \le a, b, c, d \le 10^{9}

考えたこと

まず、スタートとゴールの位置関係を平行移動して

  •  (0, 0) から  (c-a, d-b) へと移動させる問題

とみなしても変わらない。さらに対称性から

  •  (0, 0) から  (|c-a|, |d-b|) へと移動させる問題

とみなしても変わらない。よって、 p = |c-a| q = |d-b| とおいて考えることにする。まず明らかなケースとして、次のことが言える。

  •  p = q = 0 のときは、0 回
  • それ以外で  p = q のときは、1 回
  • それ以外で  p + q \le 3 のときは、1 回
  • それ以外の場合は 2 回以上かかる

また下図のように盤面全体を市松模様に塗ることにしたとき、同じ色のマスからマスへは、どんなに遠く離れていても、からなず 2 回以下で行けることに注意しよう。

f:id:drken1215:20201122222312p:plain

よって、どんなケースであってもかならず 3 手以内に到達できる。具体的には

  • 同じ色であれば 2 手 (以内)
  • 異なる色であれば、まず最初に 1 回真横に移動して (色を変える)、そこから 2 手 (以内)

というふうにすればよい。よって、明らかなケースを除いて「2 手」か「3 手」かを特定する問題だと言える。

2 手で行ける場合

1 手以内で行ける場合は予め除外した上で、2 手で行ける場合を列挙していこう。

  •  p + q が偶数のとき (スタートと同じ色のマス)
  •  p + q \le 6 のとき (1 回の移動で  p+q を 3 増やせるので)
  •  |p-q| \le 3 のとき (最初に  (p, p) まで移動して、そこから 1 手で行ける)

これら以外には行けないことが言える。念のために簡単に証明してみる。 p + q が奇数の場合を考えれば十分。 p + q が奇数のとき、2 回の移動のうちの 1 回は「色を変える移動」をする必要があるが、それが最初の移動であるとしてよい (2 回目の移動で色を変える場合であっても、1 回目と 2 回目を入れ替えても結果は変わらないため)。つまり、2 回の移動のうちの最初の移動において  |p+q| \le 3 を満たすいずれかのマスに進むものとしてよい。

そのマスから次に行けるマスを列挙すると、

  •  p + q \le 6 のとき (1 回の移動で  p+q を 3 増やせるので)
  •  |p-q| \le 3 のとき (最初に  (p, p) まで移動して、そこから 1 手で行ける)

のいずれかに限定される。

まとめ

  •  p = q = 0 のとき、0 回
  • それ以外で  p = q または  p + q \le 3 のとき、1 回
  • それ以外で以下を満たすとき、2 回
    •  p + q が偶数のとき
    •  p + q \le 6 のとき
    •  |p-q| \le 3 のとき
  • それ以外のとき、3 回

計算量は  O(1) となる。

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

int main() {
    long long a, b, c, d;
    cin >> a >> b >> c >> d;
    auto solve = [&]() -> long long {
        long long p = abs(c - a), q = abs(d - b);
        if (p == 0 && q == 0) return 0;
        if (p == q || p + q <= 3) return 1;
        if ((p + q) % 2 == 0 || p + q <= 6 || abs(p - q) <= 3) return 2;
        return 3; 
    };
    cout << solve() << endl;
}