C++で始点から目標点に到達できるかを判定するアルゴリズム

始点 (sx, sy) と目標点 (tx, ty) が与えられたとき、始点から目標点へ至る一連の移動が存在するかどうかを判定する問題を考えます。ここでいう「移動」とは、現在の点 (x, y) を (x, x+y) または (x+y, y) のいずれかに変換する操作のことです。

例として、始点が (1, 1)、目標点が (4, 5) の場合をみてみましょう。このとき答えは true になります。(1,1) → (2,1) → (3,1) → (4,1) → (4,5) という移動列が存在するためです。

解法の考え方

この問題を前方向きに素朴にシミュレーションすると、座標が指数的に増大していき非効率です。そこで有効なのが、目標点から始点へ逆向きにたどるアプローチです。逆操作では大きい方の座標から小さい方の座標を差し引くことになりますが、同じ減算が何度も繰り返されるケースがあります。そこで、この繰り返しを剰余演算（mod）でまとめて処理することで、計算量を大幅に削減できます。

具体的な手順は以下の通りです。

• tx > sx かつ ty > sy の間、次を繰り返します。
  • tx > ty の場合：tx = tx % ty
  • それ以外の場合：ty = ty % tx
• ループ終了後、次のいずれかの条件が満たされれば true を返します。
  • sx == tx かつ sy <= ty かつ (ty - sy) % tx == 0
  • sy == ty かつ tx >= sx かつ (tx - sx) % ty == 0

この手法はユークリッドの互除法と同様の仕組みで動作し、時間計算量はおおよそ O(log(max(tx, ty)))、使用メモリは O(1) と非常に効率的です。

C++による実装例

理解を深めるために、以下の実装を確認してみましょう。

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

class Solution {
public:
    bool reachingPoints(int sx, int sy, int tx, int ty) {
        while (tx > sx && ty > sy) {
            if (tx > ty) {
                tx %= ty;
            } else {
                ty %= tx;
            }
        }
        return (sx == tx && sy <= ty && (ty - sy) % tx == 0)
            || (sy == ty && tx >= sx && (tx - sx) % ty == 0);
    }
};

int main() {
    Solution ob;
    cout << (ob.reachingPoints(1, 1, 4, 5));
}

入力

1
1
4
5

出力

1

実行結果は 1（true）となり、始点 (1, 1) から目標点 (4, 5) への移動列が存在することが確認できました。