概要

本問題は、生徒を条件を満たすようにバスに割り当て、身長がバスの天井の高さより高くなって不快に思う生徒の人数を最小化する問題です。 一見複雑なグループ分けの問題に見えますが、問題の条件を整理すると、すべての生徒を「最も天井が高いバス」に割り当てるのが最適であるというシンプルな事実に帰着されます。

考察

条件の整理

問題文には以下の重要な条件があります。 1. 同じクラスの生徒は全員同じバスに割り当てなければならない。 2. \(1\) 台のバスに割り当てる人数に上限はなく、誰も割り当てられないバスがあってもよい。

最適な割り当て方の検討

生徒 \(j\) が不快な思いをしないためには、割り当てられたバスの天井の高さ \(D_i\) が、自身の身長 \(H_j\) 以上（\(H_j \leq D_i\)）である必要があります。

ここで、すべてのバスの中で最も天井が高いバスの高さ \(D_{\max} = \max(D_1, D_2, \ldots, D_N)\) に注目します。 もし、すべての生徒をこの最も天井が高いバスに割り当てるとどうなるでしょうか。

• クラスの条件: 全員が同じ \(1\) 台のバスに乗るため、「同じクラスの生徒は全員同じバスに乗る」という条件は自動的に満たされます。
• 不快な生徒の数: このバスに乗っても不快になってしまう生徒は、身長が \(D_{\max}\) よりも高い生徒（\(H_j > D_{\max}\)）のみです。

他のバス（天井が \(D_{\max}\) より低いバス）に生徒を割り当てた場合、そのバスの天井の高さは \(D_{\max}\) 未満であるため、不快になる生徒の数が減ることは絶対にありません（むしろ増える可能性があります）。

したがって、全員を天井が最も高いバスに割り当てるのが常に最適です。

結論

求める最小値は、生徒の身長 \(H_j\) のうち、バスの天井の高さの最大値 \(D_{\max}\) よりも大きいものの個数となります。 クラス名 \(S_j\) の情報は、結果に一切影響しない「ダミーの条件」であったことが分かります。

アルゴリズム

1. バス天井の高さのリスト \(D\) から、最大値 \(D_{\max}\) を求めます。
2. 各生徒の身長 \(H_j\) を順に確認し、 \(H_j > D_{\max}\) となる生徒の人数をカウントします。
3. カウントした値を答えとして出力します。

計算量

• 時間計算量: \(O(N + M)\)
  • バスの天井の高さの最大値を求めるのに \(O(N)\)、生徒の身長を走査するのに \(O(M)\) かかります。制約 \(N \leq 10^6, M \leq 10^5\) に対して十分高速に動作します。
• 空間計算量: \(O(N + M)\)
  • 入力データを保持するためのメモリ空間が必要です。

実装のポイント

• Pythonでは、入力のサイズが大きいため（\(N \le 10^6\)）、input() を何度も呼び出すと実行時間制限（TLE）になる可能性があります。sys.stdin.read().split() を用いて入力を一括で取得し、メモリ上で処理することで高速化を図っています。

• 入力データは [D_1, ..., D_N, S_1, H_1, S_2, H_2, ...] のように並んでいるため、生徒の身長 \(H_j\) はインデックス 2+N+1 から \(2\) つおきに配置されています。正解コードでは、スライス [2+N+1:2+N+2*M:2] を用いて身長データのみを効率よく抽出しています。

  ソースコード

import sys

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    N = int(input_data[0])
    M = int(input_data[1])
    
    # バス天井の高さの最大値を求める
    max_D = max(map(int, input_data[2:2+N]))
    
    # 各生徒の身長のうち、max_D より大きいものの個数をカウントする
    # 身長データはインデックス 2+N+1 から 2つおきに配置されている
    ans = sum([1 for h in map(int, input_data[2+N+1:2+N+2*M:2]) if h > max_D])
    
    print(ans)

if __name__ == '__main__':
    solve()

---

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