ABC184C Super Ryuma - モグリンの競プロ備忘録

問題リンク

問題

無限に広がるグリッド上の指定された二つの座標
$(r_1,c_1),(r_2,c_2)$
の間を次の規則に従って駒を移動させる際に、必要な最小手数を答えなさい。

駒は一手で次の条件のどれかを満たす $(a,b)$ から $(c,d)$ へのが可能である。

$a+b = c+d$ ...(移動A)
$a-b = c-d$ ...(移動B)
$|a-b|+|c-d| \leq 3$ ...(移動C)

制約

$1 \leq r_1,c_1,r_2,c_2 \leq 10^9$

考え方

この問題が茶diffなのは正直びっくりしました。そんなに簡単な場合分けかなぁ。
とりあえず問題をみてぱっと思いつくことは、

AとBの移動を一回ずつ行うことでパリティの等しいマスには最大 $2$ 手で移動できる。
上の移動にさらにCの移動を行うことで最大 $3$ 手で全てのマスに移動ができる。

ですね。つまりどのマスにも $3$ 手以内で移動できることがわかりました。ならば答えとしてあり得るのは $0,1,2,3$ の高々 $4$ つしかないんだから場合分けでいけるはず。さらに少し考えれば $0$ 手なのは当然動かない時、 $1$ 手なのは上のA,B,Cのどれかの条件を満たす時なので、 $2,3$ 手の時を場合分けできれば問題が解けたことになります。

ここで解説では $2$ 手で移動するときを丁寧に場合分けすることで求めているのですが、ここでは少し異なる解法で解いてみます。使用する典型は
"ある対象への条件を別の対象の条件に読み替える"
です。最近だとABC181F Silver Woods
atcoder.jp
が、"障害物の点にかぶらないように半径 $r$ の円を動かす"を"点を半径 $r$ の円の障害物と被らないように動かす"、に読み替えることで解く問題でした。「動かす点」に関する条件を「障害物」に関する条件に読み替えてしまうのですね。

さて、今回の問題では
" $(r_1,c_1)$ から $(r_2,c_2)$ に $2$ 手で移動できるかどうか"
を
" $(r_1,c_1)$ から $1$ 手で移動できるマスに $(r_2,c_2)$ から $1$ 手で移動できるマスが存在するかどうか"
に読み替えます。" $(r_1,c_1)$ からの移動"に関する条件を一部" $(r_2,c_2)$ からの移動"に関する条件に読み替えてしまうわけです。

ここで一番単純な方針は
" $(r_2,c_2)$ から $1$ 手で移動できるマスを全列挙してしまい、これらの中で一つでも $(r_1,c_1)$ からの移動に関するA,B,Cの条件のどれかを満たすマスが存在するかどうか求める。"
です。ただこれには問題があって $(r_2,c_2)$ から $1$ 手で移動できるマスって無限にあるんですよね、どうしよっかなー。

ここで図とじーっとにらめっこすると
" $(r_2,c_2)$ からA,Bどちらか $1$ 手で移動できるマスの中に $(r_1,c_1)$ からの移動に関するA,Bの条件のどちらかを満たすマスが存在する"
が、先ほど考えた
" $(r_1,c_1)$ と $(r_2,c_2)$ のパリティが等しい"
と同値であることがわかります。ならばあと考えるべき $2$ 手の移動は二つ、

A→C、B→C、C→A、C→Bの移動
C→Cの移動

$5$ つじゃん！！(すいません)、ともあれどの移動にもCの移動が含まれており、なおかつA→CとC→A、B→CとC→Bの移動で行けるところは各々実質変わらないことに気付けば、これらの移動については
" $(r_2,c_2)$ からCの移動 $1$ 手で移動できるマスを列挙してしまい、これらの中で一つでも $(r_1,c_1)$ からの移動に関するA,B,Cの条件のどれかを満たすマスが存在するかどうか求める。"
ことで判定可能であることに気づけます。いやー中々に骨の折れる問題だった。

コード

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

#define rep(i,n) for (int i = 0;i < (int)(n);i++)
using ll = long long;

//移動の条件を全て関数化してしまう
bool can_reach(ll a,ll b,ll c,ll d) {
  if(a+b==c+d) return true;
  if(a-b==c-d) return true;
  if(abs(a-c)+abs(b-d)<=3) return true;
  
  return false;
}

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  // cout << fixed << setprecision(15);

  ll r1,c1,r2,c2; cin>>r1>>c1>>r2>>c2;
  //移動が0手の時
  if(r1==r2&&c1==c2) {
    cout<<0<<'\n';
    return 0;
  }
  //移動が1手の時
  if(can_reach(r1,c1,r2,c2)) {
    cout<<1<<'\n';
    return 0;
  }
  //パリティが等しいとき
  if(~(abs(r2-r1)+abs(c1-c2))&1) {
    cout<<2<<'\n';
    return 0;
  }
  //(r2,c2)からCの移動1手で行けるマスが(r1,c2)から1手の移動で到達可能な時
  for(int i=c2-3;i<=c2+3;i++) for(int j=r2-3;j<=r2+3;j++) {
    if(abs(i-c2)+abs(j-r2)>3) continue;
    if(can_reach(r1,c1,j,i)) {
      cout<<2<<'\n';
      return 0;
    }
  }
  //それ以外は3手
  cout<<3<<'\n';
  
  return 0;
}