概要

\(N\) 台のバスに \(M\) 人の生徒を、同じクラスの生徒が同じバスになるように割り当てます。バスの天井の高さより身長が高い生徒は不快な思いをするため、不快になる生徒の合計人数を最小化する問題です。

考察

問題の制約として「同じクラスの生徒は全員同じバスに割り当てなければならない」とありますが、「1台のバスに割り当てる人数に上限はありません」という別の制約も存在します。 このため、複数の異なるクラスの生徒を同じバスに乗せることができます。極端な話、すべてのクラスの生徒を1台のバスにまとめて乗せることが可能です。

不快な思いをする生徒を最小限に抑えるためには、最も天井の高いバスに全員を乗せるのが最適です。 最も天井の高いバスの高さを \(max\_D\) とします。全員をこのバスに割り当てた場合、不快になる生徒は \(H_j > max\_D\) を満たす生徒のみです。 \(D_i\) の最大値が \(max\_D\) なので、\(H_j > max\_D\) を満たす生徒は、どのバスに乗っても必ず \(H_j > D_i\) となり不快になります。つまり、これらの生徒は絶対に不快を回避できません。 逆に、\(H_j \leq max\_D\) の生徒は \(max\_D\) のバスに乗れば不快になりません。

したがって、最適な割り当ては「全クラスの生徒を天井の高さが最大のバスに割り当てる」ことになり、不快になる生徒の最小人数は「身長が \(max\_D\) より大きい生徒の数」と等しくなります。

アルゴリズム

1. バスの天井の高さ \(D_i\) の中から最大値 \(max\_D\) を求める。
2. 各生徒の身長 \(H_j\) が \(max\_D\) より大きい場合、その生徒は不快になるため、その人数をカウントする。
3. カウントした人数を出力する。

計算量

• 時間計算量: \(O(N + M)\) \(N\) 個のバスの高さから最大値を見つける処理と、\(M\) 人の生徒の身長を調べる処理を行うため、全体で \(O(N + M)\) となります。
• 空間計算量: \(O(N + M)\) 入力データをすべてメモリに読み込む場合の空間計算量です。ストリーム処理を行えば \(O(1)\) まで削減可能ですが、Python等では一括読み込みが高速で推奨されます。

実装のポイント

• Pythonを用いる場合、標準入力を高速に読み込むために sys.stdin.buffer.read().split() を使用すると、処理時間を大幅に短縮できます。

• 生徒のクラス名 \(S_j\) は最適解（全員同じバスに乗せる）を考える上では不要な情報となりますが、入力をパースする際に正しく読み飛ばす必要があります。コードではインデックスを飛ばし処理（H = data[2+N+1::2]）で身長のみを抽出しています。

  ソースコード

import sys

def solve():
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    N = int(data[0])
    M = int(data[1])
    
    D = data[2:2+N]
    max_D = max(int(d) for d in D) if N > 0 else 0
    
    H = data[2+N+1::2]
    ans = sum(1 for h in H if int(h) > max_D)
    
    print(ans)

if __name__ == '__main__':
    solve()

この解説は or-glm5.2-high によって生成されました。