概要

複数のバス路線について、時刻 \(T\) 以降で最初に到着するバスの時刻を求める問題です。各路線ごとに到着時刻を計算し、その最小値を出力します。

考察

重要な気づき

各バス路線 \(i\) は時刻 \(0, A_i, 2A_i, 3A_i, \ldots\) にバスが到着します。つまり、バス路線 \(i\) の到着時刻は \(A_i\) の倍数です。

時刻 \(T\) 以降で最初に到着する時刻を求めるには、「\(T\) 以上の最小の \(A_i\) の倍数」を求めればよいです。

具体例で理解する

例えば、\(T = 7\)、\(A_i = 3\) の場合： - バス路線 \(i\) は時刻 \(0, 3, 6, 9, 12, \ldots\) に到着 - \(T = 7\) 以降で最初の到着は時刻 \(9\)

これは \(\lceil 7 / 3 \rceil \times 3 = 3 \times 3 = 9\) と計算できます。

素朴なアプローチの問題点

「時刻 \(0\) から \(1\) ずつ増やしていき、\(T\) 以降でいずれかのバスが来る時刻を探す」という方法は、\(T\) が最大 \(10^9\) になりうるため、TLE（時間制限超過）になります。

解決方法

各バス路線について、天井関数（切り上げ除算）を使って直接計算すれば、\(O(1)\) で求められます。

\(T\) 以上の最小の \(A_i\) の倍数 \(= \lceil T / A_i \rceil \times A_i\)

アルゴリズム

1. 各バス路線 \(i\) について、時刻 \(T\) 以降で最初にバスが到着する時刻を計算する
   • \(T = 0\) の場合：到着時刻は \(0\)
   • \(T > 0\) の場合：\(k = \lceil T / A_i \rceil\) として、到着時刻は \(k \times A_i\)
2. 全路線の到着時刻の最小値を求める
3. その最小値を出力する

切り上げ除算の計算

整数での切り上げ除算 \(\lceil T / A_i \rceil\) は、以下の式で計算できます：

\[k = \lfloor (T + A_i - 1) / A_i \rfloor\]

これは、\(T\) に \(A_i - 1\) を足してから切り捨て除算することで、切り上げを実現しています。

計算量

• 時間計算量: \(O(N)\)
  • 各バス路線について \(O(1)\) で到着時刻を計算し、\(N\) 路線分繰り返す
• 空間計算量: \(O(N)\)
  • 入力配列 \(A\) の格納に必要

実装のポイント

1. 切り上げ除算の実装: (T + a - 1) // a という式を使うことで、整数演算のみで切り上げ除算を実現できます。math.ceil(T / a) を使う方法もありますが、浮動小数点の誤差が心配な場合は整数演算が安全です。

2. \(T = 0\) の場合の処理: \(T = 0\) のとき、すべてのバス路線は時刻 \(0\) にバスが到着するため、答えは \(0\) です。コード中では (0 + a - 1) // a = 0 となり、正しく計算されますが、明示的に場合分けしても問題ありません。

3. オーバーフローへの注意: \(T\) と \(A_i\) が最大 \(10^9\) のとき、\(k \times A_i\) は最大で約 \(10^9\) 程度になります。Python では整数オーバーフローの心配がないため、特別な対処は不要です。

   ソースコード

import math

def solve():
    N, T = map(int, input().split())
    A = list(map(int, input().split()))
    
    min_time = float('inf')
    
    for a in A:
        # 時刻T以降で最初にバス路線aのバスが到着する時刻
        # バスは時刻 0, a, 2a, 3a, ... に到着する
        # T以上の最小のa*kを求める
        if T == 0:
            arrival = 0
        else:
            # ceil(T / a) * a
            k = (T + a - 1) // a  # ceil(T / a)
            arrival = k * a
        
        min_time = min(min_time, arrival)
    
    print(min_time)

solve()

---

この解説は claude4.5opus によって生成されました。