概要

この問題は、生徒をバスに最適に割り当てることで、不快（身長が乗車するバスの天井より高い）になる生徒の合計人数を最小化する問題です。一見複雑なグループ分け問題に見えますが、すべての生徒を「最も天井が高いバス」に乗せるという極端な割り当てを考えることで、非常にシンプルに解くことができます。

考察

1. 条件の整理と極端な割り当て

問題の条件を整理すると、以下のようになります。 - バスの定員に上限はない。 - 誰も乗らないバスがあってもよい。 - 同じクラスの生徒は同じバスに乗らなければならない。

ここで、「すべての生徒（全クラス）を、天井が最も高い \(1\) 台のバスに乗せる」という割り当てを考えてみましょう。

この割り当てを行うと、以下のことが成り立ちます。 - 全員が同じ \(1\) 台のバスに乗っているため、「同じクラスの生徒は全員同じバスに乗る」という条件を自動的に満たします。 - 天井が最も高いバスに乗っているため、不快になる生徒の数を最も少なく抑えることができます。

つまり、クラス分けやバスの複数台への分散を考慮する必要はなく、全員を「最も天井が高いバス」に集約させるのが常に最善となります。

2. 不快になる生徒の条件

バスの天井の高さの最大値を \(D_{\max} = \max(D_1, D_2, \ldots, D_N)\) とします。 全員をこの高さ \(D_{\max}\) のバスに乗せたとき、各生徒 \(j\) が不快になるかどうかは以下のように判定できます。

• 身長 \(H_j \le D_{\max}\) の生徒：天井に頭がぶつからないため、不快になりません。
• 身長 \(H_j > D_{\max}\) の生徒：このバスに乗っても天井に頭がぶつかります。また、これより高いバスは存在しないため、どのバスに割り当てても必ず不快になります。

したがって、求める最小人数は「身長 \(H_j\) が \(D_{\max}\) より大きい生徒の人数」に一致します。 クラス名 \(S_j\) の情報は、答えを決定する上で一切使用する必要がありません。

アルゴリズム

1. バスの天井の最大値の取得: \(N\) 台のバスの天井の高さ \(D_i\) を順に読み込み、その最大値 \(D_{\max}\) を記録します。
2. 不快になる生徒のカウント: \(M\) 人の生徒の情報を順に読み込みます。クラス名 \(S_j\) は無視し、身長 \(H_j\) が \(D_{\max}\) より大きい（\(H_j > D_{\max}\)）生徒の人数をカウントします。
3. 出力: カウントした人数を出力します。

計算量

• 時間計算量: \(O(N + M)\) バスの天井の高さの最大値を求めるのに \(O(N)\)、各生徒の判定に \(O(M)\) の時間がかかります。ループをそれぞれ 1 回ずつ回すだけなので、実行時間制限に余裕で間に合います。
• 空間計算量: \(O(1)\) 入力をその都度処理（ストリーム処理）し、最大値 \(D_{\max}\) とカウンターのみを保持すればよいため、配列などにデータを保存する必要がなく、メモリ使用量は極めてわずかです。

実装のポイント

• 高速入出力: \(N \le 10^6\)、\(M \le 10^5\) と入力の行数が非常に多いため、C++では std::cin の高速化（ios_base::sync_with_stdio(false); cin.tie(NULL);）を行うことで、実行時間を大幅に短縮できます。

• 変数の型: 天井の高さ \(D_i\) や身長 \(H_j\) は最大で \(10^9\) となるため、32ビット整数型（int）でも収まりますが、安全のために long long 型を使用するとより確実です。

  ソースコード

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int main() {
    // 高速入出力の設定
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    if (!(cin >> N >> M)) return 0;

    long long max_D = 0;
    for (int i = 0; i < N; ++i) {
        long long d;
        cin >> d;
        if (d > max_D) {
            max_D = d;
        }
    }

    int unpleasant_count = 0;
    for (int j = 0; j < M; ++j) {
        string s;
        long long h;
        cin >> s >> h;
        if (h > max_D) {
            unpleasant_count++;
        }
    }

    cout << unpleasant_count << "\n";

    return 0;
}

---

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