概要

各バス路線の到着時刻は一定間隔なので、時刻 \(T\) 以降に最初に来るバス（複数路線のうち最も早い到着）を求める問題です。

考察

バス路線 \(i\) は \(A_i\) 分間隔で、到着時刻は
\(0, A_i, 2A_i, 3A_i, \ldots\) のように \(A_i\) の倍数になります。

したがって「時刻 \(T\) 以降で最初に到着する時刻」は、各 \(A_i\) について - \(T\) 以上の最小の \(A_i\) の倍数

を計算し、その最小値を取ればよいです。

素朴に「時刻 \(T\) から1分ずつ進めて、どれかの路線が来るか判定する」ような方法は、\(T\) が最大 \(10^9\) なので最悪で \(10^9\) 回以上のループになり、時間内に終わりません（TLE の原因）。

ここで重要なのは、各路線ごとに「次の到着」を 直接計算できることです。

例：\(T=13, A_i=5\) のとき
到着は \(0,5,10,15,20,\ldots\) なので、\(13\) 以降最初は \(15\) です。
これは \(13\) を \(5\) で割った商を切り上げて倍にすることで求まります。

アルゴリズム

各路線の間隔 \(a(=A_i)\) について、時刻 \(T\) 以上の最小の倍数 \(t\) を求めます。

• \(t = \left\lceil \frac{T}{a} \right\rceil \cdot a\)

整数演算での切り上げは次で書けます： - \(\left\lceil \frac{T}{a} \right\rceil = \frac{T + a - 1}{a}\)（整数除算）

よって - \(t = \left( \frac{T + a - 1}{a} \right) \cdot a\)

これを全路線で計算し、最小の \(t\) を答えとして出力します。

計算量

• 時間計算量: \(O(N)\)（各路線を1回ずつ処理）
• 空間計算量: \(O(1)\)（入力配列を除けば定数）

実装のポイント

• 切り上げ計算は ((T + a - 1) // a) * a の形にすると安全で簡潔です。

• 答えの初期値は十分大きい数（例：10**30）にして最小値更新を行います。

• \(N\) が最大 \(10^5\) なので、Python では sys.stdin.readline を使うと入力が高速です。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, T = map(int, input().split())
    A = list(map(int, input().split()))
    ans = 10**30
    for a in A:
        t = ((T + a - 1) // a) * a
        if t < ans:
            ans = t
    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。