概要

バスの天井の高さと生徒の身長が与えられ、条件を満たす割り当ての中で、不快になる生徒数の最小値を求めます。

重要なのは、バスの定員に上限がなく、全員を同じバスに乗せてもよいという点です。

考察

生徒が不快になる条件は、割り当てられたバスの天井の高さ \(D_i\) より身長 \(H_j\) が大きい場合、つまり \(H_j > D_i\) のときです。

ここで、バスには人数制限がありません。また、同じクラスの生徒は同じバスに乗せる必要がありますが、異なるクラスを同じバスに乗せても構いません。

つまり、すべての生徒を「最も天井が高いバス」に乗せることができます。

バスの天井の高さの最大値を \(\max D\) とします。

• 身長が \(\max D\) 以下の生徒は、最も高いバスに乗せれば不快になりません。
• 身長が \(\max D\) より大きい生徒は、どのバスに乗っても天井より身長が高いため、必ず不快になります。

したがって、答えは

\[ H_j > \max D \]

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

例えば、バスの天井の高さが \(150, 180, 200\) であれば、最も高いバスの高さは \(200\) です。

このとき、身長 \(190\) の生徒は不快になりませんが、身長 \(210\) の生徒はどのバスに乗っても不快になります。

素朴に「クラスごとにどのバスに割り当てるか」を考えると複雑になりますが、全員を同じバスに乗せてもよいため、最大の高さだけを見れば十分です。

アルゴリズム

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

クラス名 \(S_j\) は入力として与えられますが、全員を同じバスに乗せられるため、答えの計算には使いません。

計算量

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

実装のポイント

バスの高さの最大値だけが必要なので、配列に保存する必要はありません。

また、\(D_i\) や \(H_j\) は最大で \(10^9\) なので int でも扱えますが、余裕を持って long long を使うと安全です。

クラス名は読み取る必要がありますが、計算には使わないため、そのまま無視して構いません。

ソースコード

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    long long maxD = 0;
    for (int i = 0; i < N; i++) {
        long long d;
        cin >> d;
        maxD = max(maxD, d);
    }

    int ans = 0;
    for (int j = 0; j < M; j++) {
        string S;
        long long H;
        cin >> S >> H;
        if (H > maxD) ans++;
    }

    cout << ans << '\n';
    return 0;
}

---

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