概要

各バス路線の運行間隔と目的地の施設が開く時刻 \(T\) が与えられ、\(T\) 以降で最初に到着するバスに乗る時刻を求める問題です。

考察

各バス路線 \(i\) は \(A_i\) 分間隔で運行されており、時刻 \(0\) に最初のバスが到着します。つまり、バス路線 \(i\) の到着時刻は \(0, A_i, 2A_i, 3A_i, \ldots\) となります。

高橋君は時刻 \(T\) 以降で最初に到着するバスに乗りたいので、各バス路線について、\(T\) 以降で最初に到着する時刻を計算する必要があります。これは、各 \(A_i\) について、\(kA_i \geq T\) を満たす最小の \(kA_i\) を求めることと同じです。

素朴なアプローチとして、各バス路線について \(k\) を 0 から順に増やしながら \(kA_i \geq T\) を満たす最初の \(k\) を見つける方法が考えられますが、\(T\) や \(A_i\) が最大 \(10^9\) まで大きくなるため、この方法では時間がかかりすぎます（最悪の場合 \(O(T)\) 程度になる可能性があります）。

そこで、各 \(A_i\) について \(T\) を \(A_i\) で割った商と余りを利用することで、\(T\) 以降で最初の到着時刻を \(O(1)\) で計算できます。

アルゴリズム

1. 各バス路線 \(i\) について、\(T\) を \(A_i\) で割った商を \(q\)、余りを \(r\) とします。
   • \(r = 0\) の場合: \(T\) ちょうどにバスが到着するので、到着時刻は \(T\) です。
   • \(r \neq 0\) の場合: 次の到着時刻は \((q + 1) \times A_i\) です。
2. すべてのバス路線について上記で求めた到着時刻のうち、最小のものを答えとします。

この方法では、各バス路線に対する計算が定数時間で行えるため、全体で \(O(N)\) 時間で解を求めることができます。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\) （入力の配列を保持するため）

実装のポイント

• 入力の読み取り後、各 \(A_i\) についてループを回し、\(T\) を \(A_i\) で割った余りが 0 かどうかで場合分けします。

• 最小値の初期値は十分大きな値（float('inf')）に設定します。

• 整数の除算（//）と剰余演算（%）を利用して、次の到着時刻を効率的に計算します。

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    T = int(data[1])
    A_list = list(map(int, data[2:2+n]))
    
    min_time = float('inf')
    for a in A_list:
        if T % a == 0:
            candidate = T
        else:
            candidate = (T // a + 1) * a
        
        if candidate < min_time:
            min_time = candidate
    
    print(min_time)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。