概要

全員をどのバスに割り当てるかを決め、不快になる生徒数を最小化する問題です。
実は、全員を「天井が最も高いバス」に乗せればよいため、答えは「最も高いバスより身長が高い生徒の人数」になります。

考察

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

• 1 台のバスに割り当てる人数に上限はない
• 誰も割り当てられないバスがあってもよい
• 同じクラスの生徒は同じバスに乗る必要がある

一見すると、クラスごとにどのバスへ割り当てるかを考える必要がありそうです。
しかし、バスの定員制限がないため、すべての生徒を同じバスに乗せても問題ありません。

では、どのバスに全員を乗せるのが最適でしょうか。

当然、天井が最も高いバスに乗せるのが最も不快な生徒を少なくできます。
バスの天井の高さの最大値を \(D_{\max}\) とすると、

• 身長 \(H_j \leq D_{\max}\) の生徒は、最も高いバスに乗れば不快にならない
• 身長 \(H_j > D_{\max}\) の生徒は、どのバスに乗っても不快になる

したがって、最小の不快人数は

\[ H_j > D_{\max} \]

を満たす生徒の人数です。

例えば、バスの天井の高さが

\[ 150, 180, 170 \]

なら、最も高いバスの高さは \(180\) です。
全員を高さ \(180\) のバスに乗せれば、身長が \(180\) 以下の生徒は全員快適です。
身長が \(181\) 以上の生徒だけは、どのバスでも不快になります。

素朴に「クラスごとにどのバスに乗せるか」を考えると、組み合わせが非常に多くなり、計算量が大きくなってしまいます。
しかし、全員を同じバスに乗せられることに気づけば、クラス名やクラス分けを考慮する必要はありません。

アルゴリズム

1. バスの天井の高さ \(D_i\) の最大値 \(D_{\max}\) を求める。
2. 各生徒について、身長 \(H_j\) が \(D_{\max}\) より大きいか調べる。
3. \(H_j > D_{\max}\) である生徒の人数を数える。
4. その人数を出力する。

クラス名 \(S_j\) は、答えに影響しません。
同じクラスの生徒を同じバスに乗せる必要はありますが、全員を最も高いバスに乗せればその条件も自動的に満たされます。

計算量

• 時間計算量: \(O(N + M)\)
• 空間計算量: \(O(1)\)

バスの高さをすべて保存する必要はなく、最大値だけ分かれば十分です。
また、生徒についても 1 人ずつ読みながら答えを数えればよいので、追加の配列は不要です。

実装のポイント

バスの天井の高さは、最大値だけを使います。

max_d = max(map(int, input().split()))

その後、生徒を 1 人ずつ読み込み、身長が max_d より大きければ答えに 1 を足します。

if int(h) > max_d:
    ans += 1

クラス名 s は読み取る必要がありますが、判定には使いません。

ソースコード

import sys

def main():
    input = sys.stdin.buffer.readline

    N, M = map(int, input().split())
    max_d = max(map(int, input().split()))

    ans = 0
    for _ in range(M):
        s, h = input().split()
        if int(h) > max_d:
            ans += 1

    print(ans)

if __name__ == "__main__":
    main()

---

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