JOI 一次予選 2020 (第 2 回) C - 最頻値 (6Q, 難易度 3)

集計処理を練習しよう！

• 問題へのリンク

問題概要

以上 以下の整数からなる、長さ の数列 が与えられる。

長さ の新たな数列 を次のように定義する。

• 各 に対して、 を、 を満たす の個数

の最大値を求めよ。

制約

• 

解法

問題の意味を解釈するのが難しいかもしれないですね。たとえば

• 

について考えてみましょう。1 は 1 個、2 は 3 個、4 は 2 個、5 は 1 個、7 は 1 個あり、このうち最も多いのは 2 の 3 個ですので、答えは「3」です。

これを実装するためには、問題文中に書いてある通り、数列 を求めるとよいでしょう。次のように実装できます。

vector<int> B(M+1, 0);  // M まで確保する
for (int i = 0; i < N; ++i) ++B[A[i]];  // A[i] の分を 1 個増やす

これが求められたあとは、 の最大値を求めればよいでしょう。

コード

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

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> A(N), B(M + 1, 0);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
        ++B[A[i]];
    }
    
    // B の最大値を求める
    int res = 0;
    for (int i = 1; i <= M; ++i) res = max(res, B[i]);
    cout << res << endl;
}