概要

\(N\) 系統のバスがあり、それぞれのバスは時刻 \(0\) から \(A_i\) 分おきに到着します。施設が開く時刻 \(T\) 以降で、最も早くバス停に到着するバスの時刻を求める問題です。

考察

各バス路線 \(i\) について、バスが到着する時刻は \(0, A_i, 2A_i, 3A_i, \dots\) というように、\(A_i\) の倍数（\(0\) を含む）になります。

高橋君は時刻 \(T\) 以降に到着するバスに乗りたいため、各路線 \(i\) において 「\(A_i\) の倍数のうち、\(T\) 以上である最小の数」 を探す必要があります。

数学的なアプローチ

ある路線 \(i\) の運行間隔を \(a\) とします。時刻 \(T\) 以降で最初の到着時刻を求めるには、以下の手順で計算できます。

1. \(T\) を \(a\) で割った商を考えます。
2. もし \(T\) が \(a\) で割り切れるなら、到着時刻は \(T\) そのものです。
3. もし \(T\) が \(a\) で割り切れないなら、到着時刻は \(T\) を \(a\) で割った商を切り上げたものに \(a\) を掛けた値になります。

これをプログラミング（整数演算）で簡潔に表すと、以下の式になります。 $\(\text{arrival} = \left\lceil \frac{T}{a} \right\rceil \times a\)$

Pythonなどの整数除算（切り捨て除算 //）を用いる場合、\(\lceil T/a \rceil\) は (T + a - 1) // a と書くことができます。これにより、条件分岐を使わずに「\(T\) 以上の最小の \(a\) の倍数」を計算できます。

全体の方針

すべての路線について上記の計算を行い、その中での最小値が答えとなります。\(N\) 個の路線を順番に確認していけばよいため、シンプルなループで解くことが可能です。

アルゴリズム

1. 答えを保持する変数 min_arrival を非常に大きな値（無限大など）で初期化します。
2. 各路線の運行間隔 \(A_i\) について、以下の処理を繰り返します：
   • 時刻 \(T\) 以降の最初の到着時刻を計算する： arrival = ((T + A_i - 1) // A_i) * A_i
   • もし arrival が min_arrival より小さければ、min_arrival を更新する。
3. 最終的な min_arrival を出力します。

計算量

• 時間計算量: \(O(N)\)
  • \(N\) 個の路線を 1 回ずつ走査し、各ループ内では定数時間の計算を行っているためです。
• 空間計算量: \(O(N)\) または \(O(1)\)
  • 入力値をすべてリストに格納する場合は \(O(N)\) ですが、1 つずつ読み込みながら処理する場合は \(O(1)\) で済みます。

実装のポイント

• 切り上げ処理: (T + a - 1) // a というテクニックは競技プログラミングで頻出です。

  • 例：\(T=10, a=3\) のとき、\((10+3-1)//3 = 12//3 = 4\)。\(4 \times 3 = 12\) となり、正しく求まります。
  • 例：\(T=9, a=3\) のとき、\((9+3-1)//3 = 11//3 = 3\)。\(3 \times 3 = 9\) となり、割り切れる場合も正しく動作します。

• 初期値: min_arrival の初期値は、考えられる最大値（今回の制約では \(T + \max(A_i) \approx 2 \times 10^9\)）よりも大きく設定する必要があります。Python では float('inf') を使うのが便利です。

  ソースコード

import sys

def main():
    # 全ての入力を読み込み、空白で分割してリストに格納します
    data = sys.stdin.read().split()
    if not data:
        return
    
    # N: バス路線の数, T: 施設が開く時刻
    N = int(data[0])
    T = int(data[1])
    
    # 最初にバスが到着する時刻を保持する変数
    # 十分に大きな値で初期化します
    min_arrival = float('inf')
    
    # 各バス路線の運行間隔 A_i についてループを回します
    for i in range(N):
        a = int(data[i + 2])
        
        # 各バス路線は 0, a, 2a, 3a... の時刻に到着します。
        # 時刻 T 以降で最初に到着する時刻は、a の倍数のうち T 以上の最小のものです。
        # これは ceil(T / a) * a で求められます。
        # 整数演算では ((T + a - 1) // a) * a と記述できます。
        # T = 0 の場合も、この式で正しく 0 が得られます。
        arrival = ((T + a - 1) // a) * a
        
        # これまでに見つかった到着時刻よりも早ければ更新します
        if arrival < min_arrival:
            min_arrival = arrival
            
    # 高橋君がバスに乗る時刻を出力します
    print(int(min_arrival))

if __name__ == '__main__':
    main()

---

この解説は gemini-3-flash-preview によって生成されました。