AtCoder Beginner Contest 184 C - Super Ryuma 解説

この問題がこのセットで最難……。

問題リンク

https://atcoder.jp/contests/abc184/tasks/abc184_c

問題概要

斜めにどこまででも進め、また マンハッタン距離 が 以下である場所に進める駒「超竜馬」があります。
から へ動くのに必要な最小手数を求めてください。

制約

考察

をそのまま扱ってもいいですが、マンハッタン距離の典型として「盤面を 回転する」というものがあります。これにより、マンハッタン距離がチェビシェフ距離になり計算が簡単になるというものです。今回もそれで考察が簡単になるので回転してみます。
とおくと、一回で移動できる場所は次の図のようになります。

これを見ると、 回で移動できる条件は次のいずれかを満たすときと分かります。

• 
• 
• 

これを元に、何回で移動できるかの条件を書き出します。

解法

上から順に条件を見ていって初めて合致したときの回数が答えです。

• 回で移動できる必要十分条件
  二点の座標が同じであるときです。

• 回で移動できる必要十分条件
  先程の考察にある通りです。次のうちのいずれかを満たすときです。

  • 
  • 
  • 

• 回で移動できる必要十分条件
  ちょっと難しいですが、 軸に並行に移動する回数とチェビシェフ距離が 以下の場所に移動する回数で場合分けします。

  • 回 軸に並行に移動するとき
    同じ軸に並行に移動しても仕方ないので、 軸に並行に移動したのち 軸に並行に移動します。 軸に並行に移動するときは偶数マスずつしか進めないことが図より分かるので、二点の 座標の差がどちらも偶数のとき移動できます。
  • 軸に並行に移動したのちチェビシェフ距離が 以下の場所に移動するとき
    座標の差と 座標の差のどちらかが 以下のとき移動できます。
  • 回チェビシェフ距離が 以下の場所に移動するとき
    チェビシェフ距離が 以下のとき移動できます。
    この場合は本番でのテストケースに含まれておらず、after_contest にてテストケースが追加されました。

• 回で移動できる必要十分条件
  以上以外のときは必ず 回で移動できます。

実装

実装を展開する

public static void Solve(Scanner cin)
{
    var (r1, c1, r2, c2) = cin.ReadValue<long, long, long, long>();
    var x1 = r1 + c1;
    var y1 = r1 - c1;
    var x2 = r2 + c2;
    var y2 = r2 - c2;
    if (x1 == x2 && y1 == y2)
    {
        Console.WriteLine(0);
    }
    else if (x1 == x2 || y1 == y2)
    {
        Console.WriteLine(1);
    }
    else if (Math.Abs(x1 - x2) <= 3 && Math.Abs(y1 - y2) <= 3)
    {
        Console.WriteLine(1);
    }
    else if (Math.Max(Math.Abs(x1 - x2), Math.Abs(y1 - y2)) <= 6)
    {
        Console.WriteLine(2);
    }
    else if (Math.Abs(x1 - x2) % 2 == 0)
    {
        Console.WriteLine(2);
    }
    else if (Math.Abs(x1 - x2) <= 3 || Math.Abs(y1 - y2) <= 3)
    {
        Console.WriteLine(2);
    }
    else
    {
        Console.WriteLine(3);
    }
}

ACコード: https://atcoder.jp/contests/abc184/submissions/18350763
ちゃんと after_contest も AC しています。

感想

本番嘘解法通してしまい申し訳ありませんでした。