\(A\) がどの整数をそれぞれ何個含むかという情報を求めます。 具体的には、\(((v_1, f_1), (v_2, f_2), (v_3, f_3), \ldots, (v_n, f_n))\) という列であって、

• \(A\) は整数 \(v_i\) を ちょうど \(f_i\) 個含む。
• \(v_1 \gt v_2 \gt \cdots \gt v_n \gt 0\)
• \(\sum_{i = 1}^n f_i = N\)

を満たすようなものを求めます。

例えば、\(A = (100, 200, 200, 100, 300, 100)\) であれば、 \(100\) を \(3\) 個、\(200\) を \(2\) 個、\(300\) を \(1\) 個含むので、 \(((v_1, f_1), (v_2, f_2), (v_3, f_3)) = ((300, 1), (200, 2), (100, 3))\) です。

\(((v_1, f_1), (v_2, f_2), (v_3, f_3), \ldots, (v_n, f_n))\) を得るには、 \(A\) がどの整数をそれぞれ何個含むかを調べ、それを \(v_i\) の降順に並べる必要がありますが、これは連想配列を用いることで実現できます。

\(i = 1, 2, \ldots, n\) について、\(A\) に含まれる整数のうち \(v_i\) より大きいものは \(v_1, v_2, \ldots, v_{i-1}\) の \(i-1\) 種類ですので、 \(K = 0, 1, 2, \ldots, n-1\) について、\(K\) に関する問題の答えは \(f_{K+1}\) であり、\(K = n, n+1, \ldots, N-1\) について、\(K\) に関する問題の答えは \(0\) です。

以上をまとめると、本問題に正解するには、まず連想配列等を用いて \(((v_1, f_1), (v_2, f_2), (v_3, f_3), \ldots, (v_n, f_n))\) を求め、\(f_1, f_2, \ldots, f_n\) をこの順に出力した後、\(N-n\) 個の \(0\) を出力すれば良いです。

以下に、C++ 言語による本問題の正解例を記載します。

#include <iostream>
#include <map>
using namespace std;

int main(void)
{
  int n, a;
  map<int, int> mp;
  
  cin >> n;
  for(int i = 1; i <= n; i++) cin >> a, mp[a]++;

  for(auto it = mp.rbegin(); it != mp.rend(); it++) cout << it->second << "\n";
  for(int i = 1; i <= n - (int)mp.size(); i++) cout << 0 << "\n";
  
  return 0;
}