Atcoder アルゴリズムと数学　演習問題集 058 Move on Square について

Tokageです。試験的に、Atcoderの問題の解説(?)をしてみます。プログラムはC言語で実装しています。

1.問題

図1 問題

図1のような無限に広がるマス目に、一つのコマが置かれています。あなたはこれから、「駒を上下左右に隣り合うマスに動かすという操作を ちょうどN回行わなければなりません。最初にコマが置かれたマスから右にa 個分動かした後、上に b 個分動かした場所をマス (a,b) とするとき、駒を最終的にマス(X,Y) に移動させることが可能か判定してください。

https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_ax　　より

要約すると、
原点から任意の点までに、上下と左右の移動のみで1マスずつ動き、指定された移動回数ちょうどで到着することができるかを判定する
ということです。

2.解法

この問題は、「ちょうどN回で到達しなければならない」と言う制約があるので、単に2点間の距離を計算するだけではダメです。よって、図2のように、7から10にたどり着くことが可能だけれど、N(必要な移動回数)を満たしていないので、迂回することで2マス余分に移動して、10回で到達しています。

図2 N=10場合の道筋の例

 この問題を解決するためには、移動の性質を考える必要があります。迂回を行うには、最低でも2マス移動を行う必要があるので、この問題の本質は、

 迂回が必要な場合に、迂回が行えるかどうか

 がカギになります。これを整理すると、以下のようになります。

 最小でZ回の移動で到着できるときに、Z+ 2M = Nとなるか

 (Mは任意の自然数と0の集合)

また、さらに、このように言い換えることもできます。
・最小で奇数回の移動で到着できるときは、奇数回の移動でのみ目的地にちょうど着くことができる。
・最小で偶数回の移動で到着できるときは、偶数回の移動でのみ目的地にちょうど着くことができる。
迂回には2マスの移動が必要なわけですから、当然のことです。
さて、ここまでわかったら、後はプログラムで判定するだけです。

3.プログラム

前述の解法を踏まえると、このようなプログラムとなります。今回はC言語で実装します。流れとしては、

1.標準入力を受け取る
2.到達可能か判定をする
3.出力をする
となっています。

↓プログラム全体

int main(){
  int N, X, Y;
  scanf("%d%d%d", &N,&X,&Y);
  if(abs(X) + abs(Y) <= N && ((X+Y)%2)==(N%2)){
    printf("Yes\n");
    return 0;
  }
  printf("No\n");
  return 0;
}
 

となります。ここで、Xは開始位置、Yは目標位置、Nは到達に必要な移動回数となっています。

ここで、先程の解法を思い出すと、
・最小で奇数回の移動で到着できるときは、奇数回の移動でのみ目的地にちょうど着くことができる。
・最小で偶数回の移動で到着できるときは、偶数回の移動でのみ目的地にちょうど着くことができる。
ですので、読点より前の部分と後の部分の偶奇性が一致しているかを判定してやればよいので、
条件分岐は、

if(abs(X) + abs(Y) <= N && ((X+Y)%2)==(N%2)){
printf("Yes\n");
}

のようになります。ここで、最小移動回数は当然、Nを超えてはいけないので、それも条件に入っています。