概要

\(N\) 人の参加者を、同じバスに乗るメンバー間の希望出発時刻の差がすべて \(K\) 以下になるようにグループ分けしたとき、最小で何台のバスが必要かを求める問題です。

考察

この問題の肝は、「同じバスに乗るどの 2 人の差も \(K\) 以下」という条件をいかに効率よく処理するかです。

この条件は、そのバスに乗る人のうち「最も出発時刻が早い人」を \(T_{min}\)、「最も遅い人」を \(T_{max}\) としたとき、\(T_{max} - T_{min} \le K\) であることと同値です。

最小のバス台数を求めるために、以下のステップで考えます。 1. ソートする: 出発時刻がバラバラだと扱いにくいため、まずは \(T_i\) を昇順（小さい順）に並べ替えます。 2. 端から決める（貪欲法）: 最も出発時刻が早い人は必ずいずれかのバスに乗る必要があります。その人を「そのバスで最も出発時刻が早い人（\(T_{min}\)）」に設定するのが最も効率的です。なぜなら、そのバスには \(T_{min} + K\) までの出発時刻を持つ人を全員詰め込むことができるからです。

このように、まだバスが決まっていない人のうち最も早い人を基準に、そこから \(K\) 以内の人を一つのバスにまとめる操作を繰り返す「貪欲法」で最適解が得られます。

アルゴリズム

1. 参加者の希望出発時刻 \(T\) を昇順にソートします。
2. 以下の手順でバスの台数をカウントします。
   • まだバスが割り当てられていない参加者のうち、最も出発時刻が早い人を \(T_{start}\) とします。
   • 新しいバスを 1 台用意し、出発時刻が \(T_{start} + K\) 以下の参加者をすべてそのバスに乗せます。
   • 全員のバスが決まるまでこれを繰り返します。

計算量

• 時間計算量: \(O(N \log N)\)
  • 出発時刻のソートに \(O(N \log N)\) かかります。
  • その後のバスの割り当て（リストの走査）は \(O(N)\) です。
  • 全体としてソートが支配的になります。
• 空間計算量: \(O(N)\)
  • 入力された \(N\) 人分の出発時刻を保持するためのメモリが必要です。

実装のポイント

• ソートの重要性: 貪欲法を適用するために、最初に t.sort() を行うことが必須です。

• 効率的な走査: while ループや for ループを使って、一度調べた参加者はスキップするように実装することで、無駄な計算を省けます。

• 大きな値への対応: \(N\) や \(T_i\) の値が大きいため、Python の場合は sys.stdin.read を使うなど、高速な入出力を意識すると安全です。

  ソースコード

import sys

def solve():
    # 入力を取得
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    k = int(input_data[1])
    t = list(map(int, input_data[2:]))
    
    # 出発時刻を昇順にソート
    t.sort()
    
    if n == 0:
        print(0)
        return

    # 最小のバス台数を求める貪欲法
    count = 0
    i = 0
    while i < n:
        count += 1
        # 現在のバスに乗せる最初の人の出発時刻
        start_time = t[i]
        # その人との出発時刻の差がK以内の人を同じバスに含める
        # ソート済みなので、t[i]がそのバスの中での最小値となる
        # 条件「同じバスに乗るどの2人の差もK以下」は
        # 「最大値 - 最小値 <= K」と同値
        while i < n and t[i] - start_time <= k:
            i += 1
            
    print(count)

if __name__ == "__main__":
    solve()

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