C++で同じジャンプ回数の後に2人が出会えるかどうかを判定する方法

問題概要

この問題では、2人のスタート地点と1回あたりのジャンプ距離を表す4つの整数が与えられます。求めるのは、同じジャンプ回数の時点で2人が同じ位置に出会うことができるかどうかの判定です。

具体的には、それぞれ点p1とp2からスタートし、1回のジャンプでj1とj2だけ進む2人が、ジャンプを繰り返す過程のどこかで同じ位置に到達しうるかを確認します。

例で理解しよう

入力: p1 = 5, p2 = 9, j1 = 4, j2 = 2

出力: Yes

説明:

• 1回目のジャンプ後: p1 = 9、p2 = 11
• 2回目のジャンプ後: p1 = 13、p2 = 13

2回目のジャンプの後、両者がともに位置13に達しており、ここで初めて出会っていることがわかります。

解法のアプローチ

2人がどこかの時点で出会うためには、後ろにいる人の方が、より長いジャンプができなければなりません。出会いが可能かどうかを判定するには、次の条件を確認します。

• p1 > p2 の場合(1人目が前方にいる場合)、j1 < j2 である必要がある
• かつ、((p2 − p1) % (j1 − j2)) == 0 が成り立つこと

これらの条件がすべて満たされれば出会いは可能です。そうでなければ、2人が出会うことはありません。

この条件の意味を少し詳しく見てみましょう。n回のジャンプ後に2人が同じ位置にいるということは、p1 + n×j1 = p2 + n×j2 が成り立つということです。これを変形すると n = (p2 − p1) / (j1 − j2) となります。したがって、出会いのタイミングが整数回のジャンプで訪れるためには、初期位置の差(p2 − p1)がジャンプ距離の差(j1 − j2)で割り切れなければならないのです。

ソリューションの実装例

#include<iostream>
using namespace std;

bool WillMeet(int p1, int j1, int p2, int j2){

    return ( (j1 > j2 && ( ((p2 - p1) % (j1 - j2)) == 0)) || (j2 > j1 && ( ((p1 - p2) % (j2 - j1)) == 0)) );
}

int main() {
    
    int p1 = 5, j1 = 4, p2 = 9, j2 = 2;
    if(WillMeet(p1, j1, p2, j2))
        cout<<"Both will meet at some point";
    else
        cout<<"Both will not meet at any point";
    
    return 0;
}

出力

Both will meet at some point

コードの解説

関数WillMeetは、次の2つのケースをチェックしています。

• j1 > j2 の場合: 1人目のジャンプ距離が大きいため、1人目が後方にいれば追いつける可能性があります。(p2 − p1)が(j1 − j2)で割り切れるかどうかを確認します。
• j2 > j1 の場合: 今度は2人目が追いつくケースとして、(p1 − p2)が(j2 − j1)で割り切れるかどうかを確認します。

どちらかの条件が成立すればtrueを返し、main関数ではその結果に応じて「2人はどこかで出会う」「2人は決して出会わない」という判定結果を出力します。