概要

計算量に注意しつつ,条件を適切に言い換えて実装できるかを問う問題です.

問題原案:tnodino

略解

重複する整数を持つ生徒を同一のクラスに振り分けることはできません.
この問題答えは各整数を持つ生徒の人数の最大値に一致することが証明できます.
連想配列など用いて各整数が AA に登場する回数を数えればよいです.

解説

.Ⅰ. 条件の言い換え

「ある 11 つのクラスに,等しい整数を持った生徒が 22 人以上存在しない」という条件から「等しい整数を持った 22 人以上の生徒を同一のクラスに振り分けることはではできない」ということが分かります.
こちらに沿って考えてみましょう.

.Ⅱ. 数式を用いた証明

整数 kk を持った生徒が CkC_k 人いるとします.
先述した条件により,各 kAk \in A について,クラスの個数は少なくとも CkC_k 個必要であることが生じます.
つまり,必要なクラスの個数は KKkAKCk\forall_{k \in A} K \geq C_k,すなわち KmaxkACkK \geq \max \limits_{k \in A} C_k を満たします.
これを満たす KK の最小値は maxkACk\max \limits_{k \in A} C_k です.

.Ⅲ. 登場回数のカウント

AA 要素の範囲が 10910^9 程度であることを考えると,連想配列やそれに準ずるデータ構造を用いるのがよいでしょう.

C++ では std::mapstd::unordered_map,Python では dictcollections.defaultdict などが使えます.
詳細は各言語のリファレンスや「実装例」の項を参照してください.

.Ⅳ. 発展

1)1) 類題

実装例

C++
Python