EX23 - 3.03 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MiB

説明ページに戻る

問題文

N要素の配列A_1, A_2, \ldots, A_Nが与えられます。 この配列の中の値のうち、出現回数が最も多い値とその出現回数を求めてください。

ただし、出現回数が最大になる値は複数存在しないものとします。

制約が大きいため計算量に注意してプログラムを作成してください。

制約

  • 0 \leq N \leq 10^5
  • 0 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • 出現回数が最大になるような値は複数存在しない。

入力

入力は次の形式で標準入力から与えられます。 

N
A_1 A_2 \ldots A_N

出力

値 出現回数

出現回数が最も多い値と、その出現回数をスペース区切りで出力してください。

ジャッジでは以下の入力例以外のケースに関してもテストされることに注意。

特に、ジャッジのテストケースには大きい入力が含まれているのでTLEにならないように注意してください。

入力例1

5
1 4 4 2 3

出力例1

4 2

入力の配列に含まれる各値の出現回数は以下のようになっています。

  • 1の出現回数は1回
  • 2の出現回数は1回
  • 3の出現回数は1回
  • 4の出現回数は2回

出現回数2回が最大でその値は4なので、"4 2"と出力します。

入力例2

6
3 2 3 1 3 2

出力例2

3 3

入力例3

1
1000000000

出力例3

1000000000 1

ヒント

クリックでヒントを開く

  • 「値→出現回数」の関係をmapで管理しましょう。
  • mapへの値の追加、アクセスの計算量はO(\log N)です。
  • この問題ではN^2は10^{10}なので、O(N^2)の計算量ではTLEとなります。
  • N \log Nは約1.6*10^6なので、O(N \log N)の計算量であれば間に合います。

テスト入出力

書いたプログラムがACにならず、原因がどうしてもわからないときだけ見てください。

クリックでテスト入出力を見る

テスト入力1

データが大きすぎるため省略

テスト入力2

データが大きすぎるため省略

解答例

必ず自分で問題に挑戦してみてから見てください。

クリックで解答例を見る

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

int main() {
  int N;
  cin >> N;
  vector<int> A(N);
  for (int i = 0; i < N; i++) {
    cin >> A.at(i);
  }

  map<int, int> cnt;
  for (int x : A) {
    if (cnt.count(x)) {
      // 既に含まれているならインクリメント
      cnt.at(x)++;
    } else {
      // 含まれていないなら、1を追加
      cnt[x] = 1;
    }
  }

  int max_cnt = 0;  // 出現回数の最大値を保持
  int ans = -1;     // 出現回数が最大になる値を保持
  for (int x : A) {
    // 今見ているxの出現回数が、その時点の最大よりも大きければ更新
    if (max_cnt < cnt.at(x)) {
      max_cnt = cnt.at(x);
      ans = x;
    }
  }

  cout << ans << " " << max_cnt << endl;
}