概要

生徒をクラス単位でバスに割り当て、身長が天井より高い「不快な生徒」の合計人数を最小化する問題です。実は天井が最も高いバスにすべて割り当てるのが最適で、答えは「身長が最大の天井の高さを超える生徒の数」になります。

考察

この問題で重要なのは、次の2つの条件です。

• 1台のバスに割り当てる人数に上限がない
• 誰も割り当てられないバスがあってもよい

つまり、生徒を何人でも同じバスに詰め込めます。さらに「同じクラスは同じバス」という制約がありますが、異なるクラスは別々のバスに割り当ててもよい（自由に決められる）点に注目します。

ここで、ある生徒が不快にならない条件は \(H_j \leq D_i\) です。生徒（やクラス）を割り当てるなら、できるだけ天井の高いバスを選んだ方が得です。最も天井の高いバスを \(D_{\max}\) とすると、

• \(H_j \leq D_{\max}\) の生徒は、\(D_{\max}\) のバスに乗せれば必ず快適にできる
• \(H_j > D_{\max}\) の生徒は、どのバスに乗せても天井を超えてしまうため、必ず不快になる

定員制限がないので、すべてのクラスを天井の高いバス（特に \(D_{\max}\) のバス）に同時に割り当てられます。したがって「同じクラスは同じバス」という制約は実質的に答えに影響しません。

結局、「同じクラス」という条件にとらわれず、各生徒を独立に考えてよく、答えは \(H_j > D_{\max}\) を満たす生徒の人数となります。

素朴に考えてしまう罠

「クラスごとにまとめて最適なバスを割り当てる」と複雑に考えてしまいがちですが、上限なし＋最大天井のバスにまとめられるという観察により、クラス情報や個々のバスの割り当てを一切考える必要がなくなります。クラス名 \(S_j\) はこの問題では使いません。

アルゴリズム

1. すべてのバスの天井の高さの中から最大値 \(D_{\max}\) を求める。
2. 各生徒について身長 \(H_j\) を見て、\(H_j > D_{\max}\) なら不快な生徒としてカウントする。
3. カウント数を出力する。

具体例：バスの天井が \(\{3, 5, 8\}\) のとき \(D_{\max} = 8\)。生徒の身長が \(\{4, 9, 8, 10\}\) なら、\(9\) と \(10\) の2人が \(8\) を超えるので答えは \(2\) です（\(4, 8\) の生徒は天井 \(8\) のバスに乗れば快適）。クラス名がどうであっても結果は変わりません。

計算量

• 時間計算量: \(O(N + M)\)（バスを1回走査して最大値を求め、生徒を1回走査して数えるだけ）
• 空間計算量: \(O(1)\)（最大値とカウンタのみ保持。入力を順次処理すれば追加領域はほぼ不要）

実装のポイント

• \(N\) が最大 \(10^6\) と大きいため、入力の読み込みを高速化する必要があります。本コードでは sys.stdin.buffer.read() で一括読み込みし、トークンに分割して順に処理しています。

• クラス名 \(S_j\) は答えに不要なので、読み飛ばすだけで構いません（idx += 1 でスキップ）。

• 天井の高さは配列に保存せず、読みながら最大値だけを更新すればメモリを節約できます。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    maxD = 0
    for i in range(N):
        d = int(data[idx]); idx += 1
        if d > maxD:
            maxD = d
    cnt = 0
    for j in range(M):
        idx += 1  # クラス名 S_j をスキップ
        h = int(data[idx]); idx += 1
        if h > maxD:
            cnt += 1
    sys.stdout.write(str(cnt) + "\n")

main()

---

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