C++で解く：少なくとも1人の水泳選手に会うまでの最小待ち時間を計算するプログラム

問題概要

4つの整数 p、a、b、c が与えられます。プールには3人の水泳選手がおり、それぞれ a 分、b 分、c 分かけてプールを往復します。開始時刻から数えて、1人目の選手は 0, a, 2a, 3a,… 分後にプールの左側に到着し、2人目は 0, b, 2b, 3b,… 分後、3人目は 0, c, 2c, 3c,… 分後に左側へ戻ってきます。

ここで、選手たちが泳ぎ始めてから p 分後にプールを訪れたとします。このとき、少なくとも1人の選手がプールの左側にいる状態になるまでの最小待ち時間を求めるのがこの問題です。

入力例と出力例

たとえば、入力が p = 2; a = 6; b = 10; c = 9 の場合、出力は 4 になります。

理由は次のとおりです。時刻 2 にプールに到着したとき、1人目の選手が左側に戻ってくるのは時刻 6 なので、4単位の時間だけ待つ必要があります。

解法のアプローチ

この問題は、剰余演算（mod）を使うことで非常にシンプルに解けます。

時刻 p（1始まり）にプールへ到着するとき、まず p から 1 を引いて経過時間を0始まりに補正します。その値を各選手の周期で割った余り r を調べると、現在の周期内での位置がわかります。余りが「周期 − 1」であれば選手はちょうど今そこにいるため待ち時間は 0、そうでなければ次の到着まで「周期 −（r ＋ 1）」分待つことになります。3人の選手それぞれについて待ち時間を計算し、その最小値が答えとなります。

手順

• p を 1 減らす
• (a − (p mod a ＋ 1))、(b − (p mod b ＋ 1))、(c − (p mod c ＋ 1)) の最小値を返す

C++による実装例

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

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

int solve(int p, int a, int b, int c) {
    p--;
    return min(a - (p % a + 1), min(b - (p % b + 1), c - (p % c + 1)));
}
int main() {
    int p = 2;
    int a = 6;
    int b = 10;
    int c = 9;
    cout << solve(p, a, b, c) << endl;
}

入力

2, 6, 10, 9

出力

4

まとめ

このアルゴリズムは、各選手ごとに1回の剰余演算と比較を行うだけでよいため、計算量は O(1) と非常に効率的です。周期的な出現パターンを持つ問題は、mod演算で「現在どこにいるか」を特定するのが定石なので、類題にも応用できる考え方です。