概要

すべての生徒を「天井が最も高いバス」に乗せるのが最適で、答えは「身長が最大の天井の高さを超える生徒の人数」になります。

考察

まず、この問題には一見複雑な条件が並んでいます。

• 同じクラスの生徒は同じバスに乗せる
• 各バスに人数上限はない
• 生徒は身長が天井より高いと不快になる

しかし、バスの人数に上限がないという点が非常に重要です。これにより、極端な話、全生徒を 1 台のバスにまとめて乗せてしまうことができます。全員を同じバスに乗せれば、「同じクラスの生徒は同じバスに乗せる」という制約は自動的に満たされます。

では、どのバスに全員を乗せるのが得でしょうか？

ある生徒 \(j\)（身長 \(H_j\)）に注目すると、その生徒が不快にならないためには、\(H_j \leq D_i\) となるバス \(i\) に乗る必要があります。つまり、天井が高いバスほど不快になる生徒が少なくなります。

ここで、\(N\) 台のバスのうち天井が最も高いバスの高さを \(D_{\max}\) とします。

• もし \(H_j \leq D_{\max}\) なら、その生徒は天井が最も高いバスに乗せれば不快になりません。
• もし \(H_j > D_{\max}\) なら、その生徒は \(D_{\max}\) より高い天井のバスは存在しないので、どのバスに乗せても必ず不快になります。

したがって、全生徒を天井が最も高いバスに乗せるのが最適であり、このとき不快になる生徒は \(H_j > D_{\max}\) を満たす生徒だけです。そしてこれより不快な生徒を減らすことは不可能（\(H_j > D_{\max}\) の生徒はどう頑張っても不快になる）なので、これが最小値です。

つまり、クラスの情報や個々のバスの高さの分布は実は関係なく、最大の天井の高さ \(D_{\max}\) を超える身長の生徒を数えるだけで答えが求まります。

アルゴリズム

1. \(N\) 個の天井の高さ \(D_i\) を読み込み、その最大値 \(D_{\max}\) を求める。
2. \(M\) 人の生徒について、身長 \(H_j\) を読み込み、\(H_j > D_{\max}\) となる生徒の人数を数える。
3. その人数を出力する。

クラス名 \(S_j\) は答えに影響しないため、読み飛ばすだけで構いません（全員を同じバスに乗せられるため、クラスをまとめる制約は常に満たせます）。

計算量

• 時間計算量: \(O(N + M)\)
• 空間計算量: \(O(1)\)（入力バッファを除く）

\(N\) 台のバスを 1 回走査して最大値を求め、\(M\) 人の生徒を 1 回走査して数えるだけなので、線形時間で処理できます。

実装のポイント

• \(N\) は最大 \(10^6\) と大きいため、入力の読み込みが遅いと TLE になる可能性があります。解答コードでは fread を使って一括で入力を読み込み、自前のパーサで整数や文字列を高速に処理しています。

• クラス名 \(S_j\) は使わないので、skipString のように英小文字部分を読み飛ばすだけで十分です。値を保存する必要はありません。

• \(D_i, H_j\) は最大 \(10^9\) なので int でも収まりますが、安全のため long long を使っています。答えの最大値は \(M \leq 10^5\) なので、こちらも long long で問題ありません。

  ソースコード

#include <bits/stdc++.h>
using namespace std;

int main(){
    // 高速入力
    static char buf[1 << 25];
    int len = fread(buf, 1, sizeof(buf), stdin);
    int pos = 0;
    
    auto readInt = [&]() -> long long {
        while(pos < len && (buf[pos] < '0' || buf[pos] > '9') && buf[pos] != '-') pos++;
        bool neg = false;
        if(pos < len && buf[pos] == '-'){ neg = true; pos++; }
        long long x = 0;
        while(pos < len && buf[pos] >= '0' && buf[pos] <= '9'){
            x = x * 10 + (buf[pos] - '0');
            pos++;
        }
        return neg ? -x : x;
    };
    auto skipString = [&](){
        // 空白をスキップして文字列(英小文字)を読み飛ばす
        while(pos < len && (buf[pos] == ' ' || buf[pos] == '\n' || buf[pos] == '\r' || buf[pos] == '\t')) pos++;
        while(pos < len && buf[pos] >= 'a' && buf[pos] <= 'z') pos++;
    };
    
    long long N = readInt();
    long long M = readInt();
    
    long long maxD = 0;
    for(long long i = 0; i < N; i++){
        long long d = readInt();
        if(d > maxD) maxD = d;
    }
    
    long long ans = 0;
    for(long long j = 0; j < M; j++){
        skipString();          // クラス名（不要）
        long long h = readInt();
        if(h > maxD) ans++;
    }
    
    printf("%lld\n", ans);
    return 0;
}

---

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